Föreläsning 5: Yacc

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12

Det här är ungefär vad jag tänker säga på föreläsningen. Använd det för förberedelser, repetition och ledning. Det är inte en definition av kursinnehållet, och det ersätter inte kursboken.

Idag: Yacc. Yacc-grammatikfiler. Att bygga parse-träd.

4.9 Parser generators, Yacc

Example Yacc input file (download) (kan se lite olika ut, särskilt i C-deklarationsdelen i början, beroende på Yacc-version och C-version): 

%{
  #include <stdio.h>
  #include "global.h"
  extern int tokenval;
  extern void yyerror(char*);
%}

%token DONE ID NUM DIV MOD

%%

start: list DONE
        ;

list: expr ';' list
        | /* empty */
        ;

expr: expr '+' term { printf("+"); }
       | term
       ;

term: term '*' factor { printf("*"); }
       | term MOD factor { printf("MOD"); }
       | factor
       ;

factor: '(' expr ')'
       | ID { printf("%s", symtable[tokenval].lexptr); }
       | NUM { printf("%d", tokenval); }
       ;

%%

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

int yylex(void) {
  return lexan();
}

void parse() {
  yyparse();
}

A calculator that calculates

ALSU-07 fig. 4.58 (ASU-86 fig. 4.56), med vissa ändringar (Download)

Ett fullständigt program. Bygg med t ex bison och gcc. (Eller g++.) 

%{
  #include <stdlib.h> /* Required to compile with C++ */
  #include <stdio.h>
  #include <ctype.h>
  extern int yyparse(); /* Required to compile with C++ */
  extern void yyerror(char*); /* Required to compile with C++ */
  extern int yylex(void); /* Required to compile with C++ */
%}

%token DIGIT

%%

line:	expr '\n' { printf("%d\n", $1); }
	;

expr:	expr '+' term { $$ = $1 + $3; }
	| term
	;

term:	term '*' factor { $$ = $1 * $3; }
	| factor
	;

factor:	'(' expr ')' { $$ = $2; }
	| DIGIT
	;

%%

int yylex(void) {
  int c;
  c = getchar();
  if (isdigit(c)) {
    yylval = c - '0';
    return DIGIT;
  }
  return c;
}

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

int main() {
  yyparse();
  return 0;
}

"$-grejer" (dvs attribut!): 

factor : '(' expr ')' { $$ = $2; }
expr : expr + expr { $$ = $1 + $3; }
"{ $$ = $1; }" är default: 
factor:	DIGIT { $$ = $1; }

Scannern i 2.9-programmet använder variabeln tokenval för att ange det lexikaliska värdet av en hittad token (dvs, vilket tal var det, vilken identifierare). Lex använder variabeln yylval, och det är också där som Yacc tittar för att hitta $-värdet på en token.

Som default är $-värdena heltal. Det går att ange andra datatyper än bara heltal, även flera olika i samma parser! Olika tokens och olika icke-terminaler kan ha olika typ på sitt $-resultat ($$). I deklarationsdelen av grammatikfilen: 

%union {
    double dval;
    struct TreeNode* ptr;
}

%type <ptr> expr term factor
%type <dval> num
%token <dval> NUMBER

A nice feature

%error-verbose

Priority for an ambiguous grammar

Man kan specificera operatorprioritet mycket lättare än med själva grammatikreglerna!
Ur ALSU-07 fig. 4.59 (ASU-86 fig. 4.57): 
%left '+' '-'
%left '*' '/'
%right UMINUS

...

expr :   expr '+' expr { $$ = $1 + $3; }
       | expr '-' expr { $$ = $1 - $3; }
       | expr '*' expr { $$ = $1 * $3; }
       | expr '/' expr { $$ = $1 * $3; }
       | '(' expr ')' { $$ = $2; }
       | '-' expr %prec UMINUS { $$ = -$2; }
Declaring precedence and associativity:

Some of the following examples are adapted from Thomas Niemann: A Compact Guide to Lex & Yacc.

Recursion

Left recursion (more efficient in Yacc): 
list: 
      item 
      | list ',' item 
      ;
Right recursion: 
list: 
      item 
      | item ',' list 
      ;

Varningar från Yacc

Beror (oftast) på att man har en tvetydig grammatik.

The if-else shift/reduce conflict

stmt:
      IF expr stmt
      | IF expr stmt ELSE stmt
      | ...
Yacc does the right thing, but gives a warning about a shift/reduce conflict. Use precedence to avoid the warning: 
%nonassoc IFX 
%nonassoc ELSE 

stmt:  
      IF expr stmt %prec IFX 
      | IF expr stmt ELSE stmt 
      | ...

The error token

void yyerror(char *s) { 
      fprintf(stderr, "line %d: %s\n", yylineno, s); 
}
If nothing else matches, the token error will match everything until the first of (in this case) semicolon or right curly bracket. 
stmt: 
      ';' 
      | expr ';'
      | PRINT expr ';'
      | VARIABLE '=' expr ';
      | WHILE '(' expr ')' stmt
      | IF '(' expr ')' stmt %prec IFX
      | IF '(' expr ')' stmt ELSE stmt
      | '{' stmt_list '}'
      | error ';'
      | error '}'
      ;

Synthesized Attributes

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

Inherited Attributes

decl: type varlist;
type: INT | FLOAT;
varlist:
      VAR                 { setType($1, $0); }
      | varlist ',' VAR   { setType($3, $0); }
      ;

Se även Matz Kindahls exempel.

Embedded Actions

list: item1 { do_item1($1); } item2 { do_item2($3); } item3
Inte så bra som man tror!

Debugging Yacc

...

Later:

Building parse trees

Simple (abstract syntax) trees in C: 
#define MAX_ARGS 4

enum TreeNodeType { IF, WHILE, PLUS, MINUS, TIMES };

struct TreeNode {
  enum TreeNodeType type;
  struct TreeNode* args[MAX_ARGS];
};
C++: 
class ParseTreeNode {
  // ...
};

class Stmt : public ParseTreeNode {
  // ...
};

class If : public Stmt {
  ParseTreeNode* condition;
  ParseTreeNode* then_part;
  ParseTreeNode* else_part;
};

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 13 december 2015