Konstruktor Lex
Konstruktory překladačů
z z z
Miroslav Beneš Dušan Kolář
z z
generátor lexikálních analyzátorů M. E. Lesk, 1975 - pro OS Unix flex - Vern Paxson, 1990 - GNU verze určeno pro generování výstupu v C/C++ existují i varianty pro další jazyky
Konstruktory překladačů
Konstruktor YACC z z z z
z
2
Konstruktory Lex a YACC
generátor syntaktických analyzátorů yacc = "Yet Another Compiler-Compiler" S. C. Johnson, 1975, pro UNIX bizon – kompatibilní implementace v rámci GNU projektu nadace OSF vhodné pro generování C/C++, navazuje na lex/flex
Konstruktory překladačů
3
Konstruktory překladačů
4
1
Konstruktory Lex a YACC scanner.l
parser.y
[0-9]
%term NUM %% e: e ‘+’ e | ‘(‘ e ‘)’ | NUM ;
dig %% {dig}+ .
return NUM; return yytext[0];
Konstruktory překladačů
Specifikace lex. analyzátoru definice %% pravidla %% uživatelské funkce
5
Definice z
z z
z z
z
%option case-insensitive %option noyywrap %option yylineno
z z z
Uživatelské deklarace z
z
%{ int promenna; %}
z
Definice pojmenovaných výrazů z
ws
Konstruktory překladačů
6
Vzory (regulární výrazy)
Parametry programu z
digit [0-9] %% {digit}+ return NUM; … %% void main() { while( yylex() > 0 ) {} }
z
([ \n\t]+)
Konstruktory překladačů
z
7
Znaky: a \. "/*" Množiny znaků: [a-z0-9_] [^*] [ \r\n\t] Operátory: 0*1+ 0(1|0)?1 Pravý kontext: abc/de Začátek a konec řádku: ^x x$ Expanze jména: {DIGIT} Startovací podmínka: <STR>[^"] <*>. Konec souboru: <<EOF>> Konstruktory překladačů
8
2
Postup analýzy z
z
z
Důsledky
odpovídá-li textu více vzorů, vybere se ten, který odpovídá delšímu lexému
z
z
z
vzory nemusí být disjunktní, např.
z][a-z0-9]* "print"
[a-
z
pro filtr jsou pokryty jen ty možnosti, kdy se má text modifikovat
z
pro lexikální analyzátor musí být pokryty všechny možnosti [ \n\t\r]+ [0-9]+ .
nenajde-li se žádný vzor, opisují se znaky na výstup 9
; ; { return NUM; } { return yytext[0]; }
Konstruktory překladačů
10
Předdefinované proměnné a funkce
int yylex() z generovaný lexikální analyzátor char* yytext z řetězec obsahující lexém z pozor! --- pro lex je typu char[] int yyleng z délka lexému (počet znaků v yytext) int yylineno z aktuální číslo řádku (%option yylineno) Konstruktory překladačů
{ return ID; } { return PRINT; } NE!
"//".*
Předdefinované proměnné a funkce
z
nejprve uvádíme konkrétnější, potom obecnější vzory
[0-9]+ { ... } [0-9]+(\.[0-9]+)?(E[-+][0-9]+)? { ... }
je-li takových vzorů více, vybere se první z nich
Konstruktory překladačů
z
z
z
FILE* yyin z soubor, z něhož se čte FILE* yyout
z
int input()
z
void output(char x)
z
void unput(char x)
z
z
z
z
z
11
soubor, do něhož se zapisuje čtení znaku z yyin zápis znaku do yyout
vrácení znaku do yyin
Konstruktory překladačů
12
3
Příklad - filtr
Příklad – lex. analyzátor %{ #include <stdlib.h> #define NUM 257 int intAttr; %} WHITE [ \t\r\n]+ DIGITS [0-9]+ %% {WHITE} ; {DIGITS} intAttr = strtol(yytext,NULL,10); return NUM; . return yytext[0];
%{ int num_lines = 0; int num_chars = 0; %} %% \n ++num_lines; ++num_chars; . ++num_chars; %% void main() { yylex(); printf("# of lines = %d\n", num_lines); printf("# of chars = %d\n", num_chars ); } Konstruktory překladačů
13
Konstruktory překladačů
14
Příklad – startovací podmínky
Domácí úkoly
%x POZN %% "/*"
[^*]+ "*"+[^*/]* "*"+"/"
1.
Vytvořte deterministický konečný automat přijímající všechny řetězce znaků 0 a 1, které reprezentují binární číslo dělitelné třemi. (Návod: Stavy budou odpovídat zbytkovým třídám modulo 3).
2.
Vytvořte pro lex filtr, který vypíše ze zadaného programu v jazyce C všechny řetězce. Uvažujte řetězce obsahující escape sekvence pro řídicí znaky (např. \n), speciální znaky (např. \") a znaky zadané osmičkovým (např. \377) nebo šestnáctkovým (např. \x7f) kódem.
3.
Vytvořte pomocí programu lex program, který ze zadaného programu v jazyce C odstraní všechny komentáře a nahradí je mezerou. Uvažujte rovněž situaci, kdy je otevírací komentářová závorka součástí řetězce, např. v příkazu
"//"
BEGIN(POZN); ; ; BEGIN(INITIAL);
{ int ch; while( input() != '\n' ) ; }
printf("/* %s */", str);
Konstruktory překladačů
15
Konstruktory překladačů
16
4
Deklarace
Specifikace synt. analyzátoru deklarace %% pravidla %% uživatelské funkce
%term NUM %% e : NUM | e ‘+’ e … %% void main() { yyparse(); }
Konstruktory překladačů
z
z
z
z
z
z
z
Deklarace atributů Konstruktory překladačů
18
Pravidla gramatiky e : t ‘+’ e | t ; t : f ‘*’ t | f ; f : ‘(‘ e ‘)’ | NUM ;
generické symboly – identifikátor, číslo, řetězec, ... třídy symbolů – relační operátory, aditivní operátory, multiplikativní operátory, ... kódy se přidělují automaticky
z
%term ID NUM STR IF THEN ELSE … %term RELOP ADDOP MULOP …
Konstruktory překladačů
%start e
17
jednoznakové term. symboly - ‘+’ ‘;’ pojmenované term. symboly - %term ID RELOP z
%term NUM ID
Deklarace startovacího neterminálu z
z
%{ int promenna; %}
Deklarace terminálních symbolů, jejich priority a asociativity z
Terminální symboly z
Uživatelské deklarace
z
neterminál – vše, co není deklarováno jako terminální symbol startovací neterminál z
19
podle prvního pravidla nebo %start e Konstruktory překladačů
20
5
Příklad
Asociativita
%term NUM ADDOP MULOP %% e : e ADDOP t | t t : t MULOP f | f f : '(' e ')' | NUM
_____ e + e + e ~~~~~^ %left ‘+’ %right ‘+’ %nonassoc ‘+’
Konstruktory překladačů
21
Priorita e + e * e ^ %right %left %left %right
'=' '+' '-' '*' '/' '^'
-> reduce -> shift -> error
Konstruktory překladačů
22
Příklad %term NUM %left ‘+’ ‘-’ %left ‘*’ ‘/’ %left UMINUS %% e : e '+' e | e '-' e | e '*' e | e '/' e | '-' e | '(' e ') ' | NUM
pr(+)>pr(*) -> reduce pr(+)<pr(*) -> shift nízká priorita
vysoká priorita
Konstruktory překladačů
23
Konstruktory překladačů
%prec UMINUS
24
6
Konflikty způsobené akcemi uvnitř pravidel
Sémantické akce z
z
z
e: e‘+’e { printf(“e->e+e\n”); } z Akce se provádějí během redukce a: ‘a’ { … } a => a: ‘a’ b a b: { … } z
z
z
z
{} -> C
Konflikt redukce/redukce z
25
Konstruktor javacc
z
{} -> B
B -> e / C -> e
Akce uvnitř pravidel se převedou na neterminál s e-pravidlem a akcí na konci Tato úprava může způsobit konflikty
Konstruktory překladačů
z
A -> a { a_1(); } b c ^ | a { a_2(); } b d ^
26
Formát specifikace
Generuje lexikální a syntaktický analyzátor v jazyce Java Lexikální analýza - regulární výrazy Syntaktická analýza - rekurzivní sestup, LL(k) gramatika v EBNF (rozšířená BNF s regulárními operátory)
java -cp JavaCC.zip COM.sun.labs.javacc.Main Calc.jj Konstruktory překladačů
Konstruktory překladačů
27
/* volby generátoru */ options { IGNORE_CASE = true; DEBUG_PARSER = true; } /* třída analyzátoru */ PARSER_BEGIN(Calc) public class Calc { public static void main(String args[]) throws ParseException { Calc parser = new Calc(System.in); parser.expr(); } } PARSER_END(Calc) Konstruktory překladačů
28
7
Formát specifikace
Formát specifikace
/* lexikální analyzátor */ SKIP : { " " | "\r" | "\t" } TOKEN : { < EOL: "\n" > } TOKEN : { | <SUB: "-"> | <MUL: "*"> | | <MOD: "mod"> } TOKEN : { )+ > | <#DIGIT: ["0" - "9"]> } TOKEN : { < SEMICOLON: ";" > }
/* syntaktický analyzátor */ void expr() : { } { term() (( "+" | "-" ) term())* }
Konstruktory překladačů
void term() : { } { factor() (("*" | "/" | "mod") factor())* } void factor() : { } { | "(" expr() ")" }
29
Konstruktory překladačů
30
8
