Jazyky a překladače - 5 (syntaxe 3)

27. 9. 2006 | Michal Vyskočil | Programování | 9308×

Implementace syntaktického analyzátoru není příliš snadná záležitost a konstrukce parsovací tabulky jakbysmet. Proto si představíme dva programy pro generování syntaktických analyzátorů.

Obsah

• Bison
  • Další možnosti
  • Konflikty
• Antlr
• Závěr

V předcházejícím díle jsme se seznámili se syntaktickou analýzou a s pojmy LR a LL parsery. Dnešní díl bude nadupaný kódem až po kou... koncovou kapitolu, proto asi nepotěším milovníky všeho formálního, jak tomu bylo v minulém díle.

Bison

Stejně jako flex je GNU náhrada staršího POSIXového lexu, je i bison náhradou programu yacc. Pro vysvětlení hackerského humoru — bison je druh jaka a yacc znamená yet another compiler compiler. Jedná se o generátor LR syntaktických analyzátorů a ve spojitosti s programem flex tvoří část (frontendu) překladače.

V minulém díle jsem ukazoval, že překladač jazyka C nepřeloží konstrukci printf("%s\n", n) if (n == 10);. Navíc jsem uvedl část gramatiky ve formátu EBNF, která se této části jazyka týká. Napíšeme si tedy jednoduchý analyzátor pro konstrukci if v jazyce C. Ovšem je nutné si uvědomit, že syntaxe jazyka C je velice složitá a náš příklad ukazuje pouze malou část (a to ještě ne zcela správně). To je také důvod, proč se v každém příkladu na yacc/bison, co jsem viděl, ukazuje gramatika Pascalu. Základem je tedy definiční soubor cselect.y, který obsahuje definici gramatiky.

%{
#include<stdio.h>
%}

%token IF ELSE
%token IDENTIFIER CONSTANT STRING_LITERAL
%token EQ_OP

%start compound_statement

%%

První část obsahuje potřebné definice jazyka C. Dále tu vidíme seznam jednotlivých tokenů (terminálních symbolů gramatiky). Část start označuje startovací (nonterminální) symbol gramatiky. Navíc můžeme označit aritmetické operátory slovem left — například %left "+" (případně right pro ty s pravou asociativitou). Dva znaky procento ukončují danou část a objevuje se definice gramatiky.

assignment_statement
	: IDENTIFIER '=' expression
	;

selection_statement
	: IF '(' expression ')' statement
	| IF '(' expression ')' statement ELSE statement
	;

expression
	: IDENTIFIER
	| CONSTANT
	| STRING_LITERAL
	| '(' expression ')'
	| expression EQ_OP expression
	;

statement
	: compound_statement
	| selection_statement
	| assignment_statement
	;

statement_list
	: statement
	| statement_list ';' statement
	;

compound_statement
	: '{' '}'
	| '{' statement_list '}'
	;
%%

Jak vidíte, i tato nepatrná část jazyka C potřebuje celkem 6 terminálních a 6 nonterminálních symbolů. Princip je zřejmý. Startovacím symbolem je compound_statement, který může být buďto prázdný, nebo obsahovat seznam příkazů statement_list. Seznam může obsahovat jeden nebo více příkazů, které jsou odděleny středníkem. A tak se pokračuje dále.

int main()
{
	yyparse();
}

int yyerror(char* s)
{
	fprintf(stderr, "%s\n", s);
	return 0;
}

int yylex()
{
	return 0;
}

Nakonec kód obsahuje C kód. Jak vidíme, tak hlavní parsovací funkce se nazývá yyparse. Navíc vidíme funkci yyerror, která slouží pro obsluhu chyb v průběhu parsování a potřebnou funkci lexikálního analyzátoru yylex. Zde tedy máme pouze syntaktický analyzátor, ale chybí nám lexikální. Využijeme nám známý program lex a napíšeme definici lexikálního analyzátoru.

Protože na ní není vcelku nic zajímavého, uvedu sem pouze odkazy. Lexikální analyzátor cselect.l, zvýrazněná syntaxe cselect.l.html, syntaktický analyzátor cselect.y a zvýrazněná syntaxe cselect.y.html. Případně je k dispozici archív i s Makefile — cselect.tar.gz. Pokud se podíváte do definičního souboru pro parser, zjistíte, že je funkce yylex zakomentovaná a místo ní je v kódu #include "lex.yy.c", která zařídí vložení kódu lexikálního analyzátoru generovaného programem lex.

Překlad toho celého provedeme takto:

yacc -d cselect.y
lex cselect.l
gcc -o cselect y.tab.c -lfl

Prvním příkazem vygenerujeme hlavičkový soubor y.tab.h, ve kterém jsou uvedeny makra pro jednotlivé tokeny. Navíc vygenerujeme zdrojový kód analyzátoru y.tab.c. Varování o shift/reduce konfliktech jsou způsobená nejednoznačnostmi v definici gramatiky. Při spuštění programu můžeme zadávat vstup:

$ ./cselect
{ a = b }
^D
$ ./cselect
{ if ( a == b ) { s = 1; gid = 0 }}
^D
$ ./cselect
a = b
parse error
$ ./cselect
{ a = b; }
parse error

Jak vidíme, parser skutečně provádí kontrolu podle zadané gramatiky. Například v ní není povoleno, aby poslední příkaz v seznamu končil středníkem. Rovněž není žádné zotavení se z chyb (což není nikterak jednoduchá věc a pro podrobnosti konzultujte dokumentaci), takže náš zárodek překladače je ekvivalentem jedné úpravy gcc, která vrací true, pokud je program dobře napsán a false, pokud špatně. Z reálně používaných programů dostávám stejně užitečná hlášení z MSIE — Na stránce se vyskytla chyba.

Další možnosti

Zatím náš program nepředával žádné hodnoty mezi skenerem a parserem. K tomu slouží proměnná yyval, takže můžeme do definice skeneru napsat [0-9]+ {yyval = atoi(yytext); return CONSTANT;}. Jenže yyval je implicitně typu int. Naštěstí bison dovoluje definovat vlastní typ proměnné, takže do definice parseru přidáme

%union {
	int integer;
	char* string;
}
...
%token <integer> CONSTANT
%token <string> IDENTIFIER

a definice parseru se změní na [0-9]+ {yyval.integer = atoi(yytext); return CONSTANT;}

Při průchodu stromem potřebujeme při nalezení pravidla udělat nějakou akci. Například:

expression
	: IDENTIFIER {printf("nalezen identifikátor %s\n", $1);}
	;

Pokud vás zaráží $1, pak vězte, že jde o makro, které představuje odkaz na zásobník hodnot, které analyzátor spravuje. Například aritmetické operace se dají psát takto:

expression:
	: expression '+' expression { $$ = $1 + $3; }

Konflikty

Gramatiky nebývají jednoznačné a nástroje jako yacc je odhalují. V našem případě se jedná mj. o problém volné klausule else, kterou trpí mnoho jazyků. Pokud zapíšeme kód

if (a == b) if (b > c) do_anything else do_anything2

Překladač neví, ke kterému z obou if patří klauzule else. Při zpracování totiž překladač může provést reduce a uzavřít pouze první if, anebo shift pokračovat ve čtení dalšího tokenu a zpracovat if-else. Implicitně yacc provádí přesuny tak dlouho, dokud nezíská nejdelší vstupní řetězec, takže klauzule else se přiřadí druhému if, což je stejné chování, jaké programátoři v C (Pascalu a podobných jazycích) očekávají. Pro jednoznačný zápis musí programátor napsat {}. Ovšem bison umožňuje přiřazovat některým větvím gramatiky prioritu. Například v jazyce Python tato situace nemůže nastat, protože tam jsou bloky přesně definovány odsazením.

Antlr

Program s více než podivným názvem (znamená Another toolkit for language recognizer) způsobil menší pozdvižení v oblasti překladačů. Do té doby se všeobecně uznávalo, že není možné efektivně implementovat LL(n > 1) gramatiku (pro připomenutí, gramatiku, která potřebuje pro rozhodování více než jeden token). Ostatně, bez ohledu na snahy Niclause Wirtha dávali vývojáři přednost LR parserům, jejichž implementace byly považovány za efektivnější. Tento program, napsaný v Javě, mínění vývojářů změnil. Podotýkám, že název, který končí na LR, mnoho vývojářů mate, ale nemá to nic společného s LR parsery, program skutečně generuje LL(n) gramatiky. Nejsme tedy omezeni na C, nebo C++, jako je tomu v předchozím případě.

Mezi jeho další výhody patří to, že generuje kód pro analýzu rekurzivním sestupem, který je čitelnější než výstup LR analýzy bisonu. Také dokáže generovat překladač pro čtyři prostředí — Java, v níž je napsán, C#, C++ a Python. Jeho Public Domain Licence navíc nikterak nebrání integraci do dalších produktů, jako je třeba Intelli Idea (viz seznam). Případně dokáže vygenerovat kód pro průchod syntaktickým stromem, obsahuje podporu i pro sémantické akce (ve skutečnosti jí trochu obsahuje i bison).

Ukážeme si kousek analyzátoru (popravdě se jedná o upravený příklad ze stránek anltr.org):

{
	import java.io.*;

	import antlr.CommonAST;
	import antlr.DumpASTVisitor;
}

class P extends Parser;

startRule
	:   o:Constant
	{System.out.println("Constant: "+o.getText());}
	|   i:ID
	{System.out.println("ID: "+i.getText());}
	;

{
	import antlr.*;
}

class L extends Lexer;

// one-or-more letters followed by a newline

Constant
	: '1'..'9' ( Digit )* NEWLINE
	| '0' ( 'x' | 'X' ) ( 'a'..'f' | 'A'..'F' | Digit )+ NEWLINE
	;

ID:   ( Char ) ( Char | Digit |'_' )+ NEWLINE
	;

NEWLINE
	:   '\r' '\n'   // DOS
	|   '\n'        // UNIX
	;

protected Digit:    '0'..'9' ;
protected Char:     'a'..'z' | 'A'..'Z' ;

Jak vidíme, je možné prakticky kdekoliv v kódu psát kód v Javě. Ve výše zmíněném příkladu definujeme třídu pro parser i scanner v jednom souboru (na rozdíl od kombinace flex/bison). Dalším rozdílem je to, že je překladač objektový, takže máme třídu P pro parser a L pro lexikální analyzátor. Ovšem takový kód sám od sebe nedělá nic, je nutné objekty inicializovat a zavolat.

import java.io.*;

class Main {
	public static void main(String[] args) {
	try {
		// vytvoreni scanneru
		L lexer = new L(new DataInputStream(System.in));
		// vytvoreni parseru
		P parser = new P(lexer);
		// zavolani startovaci podminky
		parser.startRule();
	} catch(Exception e) {
		System.err.println("exception: "+e);
	}
	}
}

Po instalaci balíčku jsem ze skriptu /usr/bin/runantlr zjistil potřebnou CLASSPATH tak, abych mohl analyzátor přeložit.

$ export CLASSPATH=$CLASSPATH:/usr/share/java/antlr.jar
$ java antlr.Tool grammar.g
ANTLR Parser Generator   Version 2.7.6 (20060511)   1989-2005
$ javac *.java

A používáme:

$ java Main
120
Constant: 120
$ java Main
identifikator
ID: identifikator
$ java Main
0112
exception: line 1:2: unexpected char: '1'

Závěr

V tomto díle jsme si představili dva nástroje pro tvorbu syntaktických analyzátorů. Je třeba si uvědomit, že oba dva generují parsery pro podmnožinu bezkontextových gramatik a proto, pokud vyžadujeme plnou sílu gramatiky, musíme využít jiné nástroje založené na jiných algoritmech. Přestože je kombinace yacc/bison součástí prakticky libovolného unixového systému, myslím, že program antlr stojí za pozornost.

Existuje ovšem daleko větší řádka překladačů překladačů (jak se tyto nástroje nazývají).

Essence	Generátor LR parserů pro Scheme
GOLD Parsing System	Generátor LALR gramatik, který se pyšní největším počtem podporovaných cílových jazyků. Vedle C, Javy nebo Pythonu umí generovat kód pro x86 assembler nebo Visual Basic.NET.
javaCC	Další z řady LL(n) generátorů pro Javu.
SableCC	Generátor LALR parserů pro Javu (umí i C, C++, OCAML, Python a C#).
SmaCC	Generátor LR a LALR parserů pro Smalltalk.
cl-yacc	LR generátor pro Common Lisp.
SPARK	Implementace Earlyho parsovacího algoritmu v Pythonu.
CYK Parser c C++	Implementace algoritmu CYK v C++

Tímto vynecháme syntaxi a posuneme se dále. Velkou otázkou příštího dílu bude — co to vlastně znamená? V terminologii počítačových vědců sémantika. A s tím související otázku typů. Navíc si konečně ukážeme schéma překladače.

       

Komentáře

[jan.xxx]

Kdysi jsem přemýšlel, že bych tím projel jeden textový formát souborů a naparsoval bych to do nějakych tříd. Ale přijde mi to nějak složité. Asi ze mě programátor nikdy nebude

[Ladislav Thon]

Implementace syntaktického analyzátoru není příliš snadná záležitost

Implementace parseru (v ruce) je při použití rekurzivního sestupu velmi snadná záležitost. IMHO neexistuje důvod, proč navrhovat programovací jazyky jinak než jako LL(1), takže rekurzivní sestup je úplně v klidu. Z důvodu, který mi není známý, bohužel někdo s oblibou navrhuje LR prasárny typu C, které navíc obsahují příšerné množství konfliktů...

yacc -d cselect.y
lex cselect.l

Já myslel, že používáme bison a flex

ANTLR ... program skutečně generuje LL(n)

ANTLR používá predikátové LL(k) gramatiky, takže má dokonce větší vyjadřovací schopnosti než LALR. A to se vyplatí

[Vašek Lorenc]

Implementace syntaktického analyzátoru není příliš snadná záležitost

Implementace parseru (v ruce) je při použití rekurzivního sestupu velmi snadná záležitost.

Ještě snazší je implementace parseru např. v Haskellu za pomoci monadických parserů. Nebo pomocí generátoru parserů Happy, nicméně to první řešení je mnohem elegantnější.

[Ladislav Thon]

Ještě snazší je implementace parseru např. v Haskellu za pomoci monadických parserů.

To jsem neznal. A neznám. A věřím tomu, že při vysokoúrovňových funkcionálních orgiích mohou vzniknout nádherné parsery Nicméně z toho, co jsem tak za pár minut stihl najít, to vypadá, že v principu jde též o rekurzivní sestup. Wirthův přístup má ještě své zastánce!

[Kyosuke]

http://codepoetics.com/code/parser.py

http://chneukirchen.org/blog/archive/2005/10/the-rightyear-parsing-library.html

Dobré zboží se prodává samo…

[Tom.š Ze.le.in]

yacc -d cselect.y
lex cselect.l

Já myslel, že používáme bison a flex

A proč by se binárka bisona neměla jmenovat yacc? :)

[Ladislav Thon]

A proč by se binárka bisona neměla jmenovat yacc? :)

Uff, jestli se binárka bisona jmenuje yacc, tak jsem silně konsternován. Ještě že to nepoužívám, musel bych si začít klást otázky, proč se binárka Linuxového kernelu nejmenuje minix

[Michal Vyskočil]

# cd /usr/bin
# ln bison yacc
# rm bison

Kontrolní otázka, jakže se teď jmenuje binárka bisonu

[Michal Kubeček]

Jmenovat se tak může, stejně prakticky ve všech linuxových distribucích jsou lex a yacc jen linky na flex a bison (stejně jako třeba sh na bash a vi na vim). Pokud ji ale spouštíte jménem lex resp. yacc, neměl byste použít nic z rozšíření, která mají flex resp. bison navíc.

[Michal Vyskočil]

No, v Linuxových distrech se stejně používá bison a flex. Ale tohle mi jelo i na prastaré Sunovské mašince

ANTLR používá predikátové LL(k) gramatiky, takže má dokonce větší vyjadřovací schopnosti než LALR. A to se vyplatí

Predikátové, to slovo mě vypadlo. Díky za upozornění.

[hypiz]

jen drobna korekce, LL(k) a LALR(1) jsou neporovnatelne, .. nebo snad ne?

[Pavel Kysilka]

skvele, to jsem presne shanel. o bisonu vim, ale pro javu to je horsi.

mnohokrate diky.

gf

[ehmmm]

Co se tyka konfliktu s if/else, tak v Python jde neco, co asi jde i v C.

a if b else c if d else e

Ma to byt?: a if b else (c if d else e)

Nebo?: (a if b else c) if d else e

Intuitivne si myslim, ze se to bude chovat jako ta prvni varianta.

Ale uznavam, ze to nema na ceckovske if (a) if (b) {c;} else {d;}