SEG-2506 - Construction de logiciel - Hiver 2016

Devoir 2 - Analyse lexicale

Donné: 22 février - Remise: vendredi, le 11 mars pendant la session de lab - Vous pouvez travailler en groups de deux.

À remettre: Le rapport SUR PAPIER. Fichiers Lex dans un fichier zip dans un courriel au TA.

1. Trouver des expressions régulières pour des langages (15 points)

Trouvez des expressions régulières qui définissent les langages suivants:

1. Les tags XML. Les tags débutants peuvent contenir des attributs. La forme des tags est montrée par les exemples suivants:
• Tag débutant: <name-x attribute-1="some string" attribute-2="xyz">
• Tag débutant avec indication de terminaison: <funny laugh123="go" s-t-o-p=";>"/>
• Tag de terminaison: </name-x>
• Note: L'alphabet contient les ensemble alpha, digit and {-,<,>,/, ", =, ; }.
2. Toutes les chaînes sur l'alphabet  {a,b} qui ne contiennent pas la sous-chaîne aba.
3. Toutes les chaînes sur l'alphabet  {a,b} dont le nombre des "a" est un multiple de trois (zéro inclu).

Clarifications:

• tab names and attribute names have the usual form of identifiers, except that the "-" character may also be used.
• For the definition of the regular expressions, you may use the following extensions to the basic operators: +, ?, character class; but not ^ .
  

2. Trouvez des automates accepteurs (15 points)

Pour chaque langage défini sous point (1), trouvez un automate accepteur déterministe qui accepte exactement ce langage.

3. Comparaison d'expression régulières (20 points)

Nous considérons les pairs d'expressions régulières suivants. Pour chaque pair, indiquez si les deux expressions désignent le même langage ou non. Si elle désignent le même langage, donnez une preuve de l'égalité des langages en utilisant les propriétés algébriques des opérateurs des expressions régulières. Si elle désignent des langages différents, donnez un exemple de chaîne qui fait partie de l'un des langages mais pas de l'autre.

1. (a|b|c)*                  a*|b*|c*
2. a(b|c)|(aa|bb)c       (ac|bbc|ab|aac)
3. a(bca)*bc              ab(cab)*c
4. a (b*a|cba)*           (ab*|acb)*a

4. Construire un analyseur lexical en utilisant Lex (50 points)

Votre tâche: Construire un analyseur lexical pour une version simpifiée du langage Pascal. L'analyseur devrait compter le nombre d'occurences (dans un programme) des identificateurs (incluant les mots clés et mots réservés), des nombres, de lignes de programme, et des commentaires. Note: pour cette exerice, vous devriez compter les mots clés et mots réservés comme des identificateurs.

Méthode: Vous devriez utiliser Lex (ou Flex) comme vous avez fait dans le Lab-5.

Information: Vous trouvez ci-dessous une définition de la syntaxe de Pascal, quelques notes sur l'analyse lexicale, et un exemple d'un programme simple en Pascal. La syntaxe est définie dans une notation BNF - il n'est pas nécessaire de comprendre cette notation en détail. Voici quelques explications concernant la notation utilisée dans la définition de la grammaire`

• Des mots en italic représentent des non-terminaux (identificateur de sous-langages) que vous pouvez ignorer. Ils sont important pour l'analyse syntaxique.
• Les unités lexicales id et num sont expliquées en bas.
• Les mot écrits en gras sont principalement des mot clés ou des mots réservés (par exemple program, array, etc.). Vous devriez les compter comme les identificateurs.
• D'autres caractères, comme [, ], :, ;, (, ), sont aussi des unités lexicales. Elles ne sont pas à être comptées.
• Quelques mots écrits en gras sont des opérateurs, comme assignop (operateur d'affectation, ":="), ou relop (operateur de comparaison, e.g. "<", ">", etc.) et autres.

Définition de la syntaxe:

Un exemple de programme en Pascal