What is a Grammar Rule (in Parsing)?

Question

I am trying to write an interpreter but am having difficulty understanding the theoretical underpinnings of the process.

I understand that the first part is to write a lexer which splits the string up into a list of valid tokens and then a parser is used to generate the corresponding abstract syntax tree for this string of tokens. However, a parser is built using a grammar rule, which is what I'm having difficulty understanding.

A Grammar rule is obviously used to create the rules of the resulting abstract syntax tree, but how exactly does this middle step work. Does it pattern match on string characters and a specific list of tokens or . . .?

Any type of intuition or explanation is welcomed. Thanks!

Answer 1

Search the internet for lex/yacc examples and tutorials. Learning by doing. Ability to program in C is also necessary.

http://ds9a.nl/lex-yacc/cvs/lex-yacc-howto.html

lex is the ancient Unix lexer, which generates C-code from a regexp based spec. yacc is the ancient Unix parser for building syntax trees. It generates C code too.

The modern GNU versions of the tools are called flex and bison.

Here's the core of the yacc code of a calculator. It shows how higher level constructs are built from the tokens, and what to do when such constructs are encountered.

%%
list : // empty
     | list stm '\n'         { print(); }
     | list cmd '\n'         { print(); }
     | list cmd stm '\n'     { print(); }
     | list stm cmd '\n'     { print(); }
     | list cmd stm cmd '\n' { print(); }
     | list error '\n'       { yyerrok; print(); }
     ;
cmd  : COMMAND               { commands[$1](); }
     ;
stm  : expr                  { output = $1; outputPush(); }
     | VAR '=' expr          { vars_set($1, &$3); }
     ;
expr :                       { outputGet(); $$ = output; }
     | '_'                   { outputGet(); $$ = output; }
     | '(' expr ')'          { $$ = $2; }
     | expr OPADD expr       { $$ = tNumOpIn ($1, $2, $3); }
     | expr OPMUL expr       { $$ = tNumOpIn ($1, $2, $3); }
     | expr OPPOW expr       { $$ = tNumOpIn ($1, $2, $3); }
     | OPPRE expr            { $$ = tNumOpPre($1, $2); }
     | VAR                   { if (vars_get($1,&$$)) $$=output; }
     | NUMBER                { $$ = $1; }
     ;
%%