previous next contentsnanoPascal
nanoPascal (a very poor subset of Pascal) from
R. Gerady: Experimental Comparison of Some Parsing Methods. SIGPLAN Notices 22, 79-88 (1987)
. Its syntax is given in Listing 1. The taken EBNF notation is based on N. Wirth's suggestions. All literal terminals must be quoted. Identifiers for productions (= nonterminals) must start with a letter and can contain digits or letters. There are some restrictions regarding the number of significant characters and forbidden names. See the installation guide for detailed information. (Identifiers are propagated into the host language programs to make them better readable. Thus, one has to avoid clashes with the host language's keywords.)
program = block '.'.
block = ['VAR' ident {',' ident} ';']
'BEGIN' statement {';' statement } 'END' .
statement = 'WRITE' expression |
'READ' ident|
ident ':=' expression |
'BEGIN' statement {';' statement } 'END' |
'IF' expression 'THEN' statement ['ELSE' statement] |
'WHILE' expression 'DO' statement | .
expression = simpleExpr
[('='|'<'|'>'|'<='|'>='|'<>') simpleExpr ].
simpleExpr = ['+'|'-'] term
{('+'|'-'|'OR') term }.
term = factor {('*'|'DIV'|'AND') factor}.
factor = ident | num | '(' expression ')'| 'NOT' factor.
(1) In expression the order of comparisons must be rearranged to:
expression = simpleExpr [('='|'<='|'>='|'<'|'>'|'<>') simpleExpr ].(2) Rather similar, in factor one has to move the ident branch to the end (or at least after the 'NOT' factor branch):
factor = num | '(' expression ')'| 'NOT' factor | ident.Here, this is enough to create a parser for the nanoPascal language from the slightly modified EBNF description.
Now you can generate a parser for this simple language by processing each of its rules, i.e. by their translation. In fact, you are producing a bundle of mutually dependent parsers as - in principle - every nonterminal can act as root of a (sub-)language.
If this language processor parses some input it delivers just a boolean value (true - text belongs to the defined language resp. false - otherwise). This state may be sent to the log.
ex1= ident -> ident_. would accept an identifier and translate it into itself.
The translation of a sequence of numbers like 1 2 3 into a reverted list 3,2,1
would be described by
ex2= num [ ex2] -> [ex2_ ','] num_.
We will demonstrate the step by step implementation of a translator. It is useful to insert some default (maybe empty) target generation into each rule first to avoid error messages when applying productions, which have not been supplemented yet. Now it is possible to check the target description of every translation rule individually.
Let us begin with the translation of variable declarations, which are an optional component of block. Here nothing is known about their type but it seems sensible to assume them as integer ones. I.e., some text VAR a,b,c; should be translated into int a,b,c;.
Thus we will get
block = ['VAR' id:ident {',' ident[i]} ';']
'BEGIN' statement {';' statement} 'END'
-> ['int ' id_ {',' ident_[i]} ';\n'].
block = ['VAR' ident {',' ident[i]} ';']
'BEGIN' statement {/..c/';' statement[i] } 'END'
-> ['int ' ident_ {',' ident_[i]} ';\n']
'main() \n{\n' statement_ {/..c/ '\n' statement_[i] } '}\n'.
VAR a,b,c; int a,b,c;
BEGIN main(){
a:= 2; into STATEMENT
IF b<3 THEN c:= a STATEMENT
END }statement = 'WRITE' expression |
'READ' ident|
'BEGIN' statement[1] N:=0; {';' statement[i+1] } 'END' |
'IF' expression 'THEN' st:statement ['ELSE' ste:statement] |
'WHILE' expression 'DO' st:statement |
ident ':=' expression |
-> 'WRITE ' |
'READ ' |
'COMPOUND ' |
'IF '|
'WHILE ' |
':= '|
'EMPTY '.and then substitute the strings by correct descriptions. The handling of semicolons and line feeds needs some care for a fairly pretty looking result. The translation of the compound statement uses an index shift to avoid renaming. The empty statement is silently included as last (empty) branch in both the source and the target.
In the same way a translator for expression etc. can be developed. Listing 2 shows the complete description. T he rule for term illustrates the use of an additional data structure for preserving branch information in an iterative alternative structure.
program = block '.' -> '#include <stdio.h>\n' block_ .
block = ['VAR' ident {',' ident[i]} ';']
'BEGIN' statement {/..c/';' statement[i] } 'END'
-> ['int ' ident_ {',' ident_[i]} ';\n']
'main() \n{\n'
statement_ {/..c/ '\n' statement_[i] }
'}\n'.
statement = 'WRITE' expression |
'READ' ident|
'BEGIN' statement[1] {';' statement[i+1] } 'END' |
'IF' expression 'THEN' st:statement ['ELSE' ste:statement] |
'WHILE' expression 'DO' st:statement |
ident ':=' expression |
-> 'printf("%d",' expression_ ');' |
'scanf("%d", &' ident_ ');' |
'{' {/..N+1/ statement_[i] '\n' } '}' |
'if (' expression_ ') ' st_ ['else ' ste_ ]|
'while (' expression_ ') ' st_ |
ident_ '=' expression_ ';'| .
expression = simpleExpr
[('='|'<='|'>='|'<>'|'<'|'>') sE: simpleExpr ]
-> simpleExpr_
[('=='|'<='|'>='|'!='|'<'|'>') sE_ ].
simpleExpr =
VAR op: FLEX OF INT;
['+'|'-'] term
{(/op[i]/'+'|'-'|'OR') term[i] }
-> ['+'|'-'] term_
{(/op[i]/'+'|'-'|'||') term_[i] }.
term =
VAR op: FLEX OF INT;
factor {(/op[i]/'*'|'DIV'|'AND') f2:factor[i]}
-> factor_ {(/op[i]/ '*'|'/'|'&&') f2_[i]}.
factor = num | '(' expression ')'| 'NOT' factor | ident
-> num_ |'(' expression_ ')'|'!' factor_ | ident_ .A small example translation is given in Listing 3. Of course, some things could still be improved, but let us mention that up to now this translation is defined on a purely syntactic level. Whether these are pros or cons, depends from the application context. The main advantage of the restriction to syntax is its simplicity. A possible drawback may be that so called semantic errors, e.g., missing declaration, in the source are not detected. The consequences may vary depending from how strict generated targets are checked in subsequent steps. If errors are reliably caught later on, it may be a matter of taste where to find them out in the most sensible way.
SOURCE TARGET
VAR X, Y, H, GGT; #include <stdio.h>
BEGIN int X,Y,H,GGT;
READ X; READ Y; main()
WHILE X<>0 DO {
BEGIN scanf("%d", &X);
IF X<Y THEN BEGIN scanf("%d", &Y);
H:= X; X:= Y; Y:= H while (X!=0) {if (X<Y) {H=X;
END; X=Y;
X:= X-Y; Y=H;
WHILE X<Y DO X:= X-Y }
X:= X-Y X=X-Y;
END; while (X<Y) X=X-Y;
GGT:= Y; WRITE GGT }
END. GGT=Y;
printf("%d",GGT);}Finally, let us add a translator which converts nanoPascal programs into XML representations reflecting the grammar. It can be applied to the same source. Its output gives a striking impression of the advantages of syntax based notations if they are intended to be read by humans. Remarkably, without adding any information or making decoding significantly easier the size of the XML description is more than twice the size of the original document.
program = block '.' -> '<program>' block_ '\n</program>'.
block = ['VAR' ident {',' ident[i]} ';']
'BEGIN' statement {/..c/';' statement[i] } 'END'
-> '\n<block>' ['\n<ident value= "' ident_ '"/>' {'\n<ident value= "' ident_[i]'"/>'} ]
statement_ {/..c/ statement_[i] }
'\n</block>'.
statement = 'WRITE' expression |
'READ' ident|
'BEGIN' statement[1] {';' statement[i+1] } 'END' |
'IF' expression 'THEN' st:statement ['ELSE' ste:statement] |
'WHILE' expression 'DO' st:statement |
ident ':=' expression |
-> '\n<statement action= "write">' expression_ '\n</statement>' |
'\n<statement action= "read"> <ident value= "' ident_ '"/>\n</statement>' |
{/..N+1/ statement_[i] } |
'\n<statement action= "if">' expression_ ' ' st_ [' ' ste_ ]'\n</statement>'|
'\n<statement action= "while"> ' expression_ ' ' st_ '\n</statement>'|
'\n<statement action= "="><ident value= "' ident_ '"/> ' expression_ '\n</statement>'| .
expression = simpleExpr
[('='|'<='|'>='|'<>'|'<'|'>') sE: simpleExpr ]
-> '\n<expression>' simpleExpr_
['<operator="'('=='|'<='|'>='|'!='|'<'|'>')'"/>' sE_ ] '\n</expression>'.
simpleExpr =
VAR op: FLEX OF INT;
['+'|'-'] term
{(/op[i]/'+'|'-'|'OR') term[i] }
-> '\n<simpleexpression>' ['<sign value="' ('+'|'-') '"/> '] term_
{(/op[i]/'+'|'-'|'||') term_[i] } '\n</simpleexpression>'.
term =
VAR op: FLEX OF INT;
factor {(/op[i]/'*'|'DIV'|'AND') f2:factor[i]}
-> '\n<factor> 'factor_ {'<operation="'(/op[i]/ '*'|'/'|'&&')'"/>' f2_[i]} '\n</factor>'.
factor = num | '(' expression ')'| 'NOT' factor | ident
-> '<number value="' num_ '"/>'
| expression_
|'<neagtion> ' factor_ '</negation>'
| '<ident value= "' ident_ '"/> '.Suggestion: One may consider it a interesting exercise to write a translator which builds XML DTDs (or similar) from EBNF grammars.
previous next contents