Laboratorium 5: generatory parserów

Bison

Omawiamy przykład, np. kalkulator dla ONP

%{
#define YYDEBUG 1
#include <stdio.h>
 double atof(const char *s);
int yylex();
void yyerror(const char *s);
#define YYSTYPE double
%}
%token NUM
%% 
input:    /* empty */
        | input line 
        ;
line:     '\n'
        | exp '\n' { printf("\t%.10g\n", $1);}
        ;
exp:    NUM           { $$ = $1;      }
        | exp exp '+' { $$ = $1 + $2; }
        | exp exp '-' { $$ = $1 - $2; }
        | exp exp '*' { $$ = $1 * $2; }
        | exp exp '/' { $$ = $1 / $2; }
%%
void yyerror(const char * s) { puts(s); }
int main() {
   yydebug=0; /* 1 for debugging */
  yyparse();
}

Java CUP

Omwiamy przykład, np.

import java_cup.runtime.*;
 
terminal Integer NUM;
terminal SEMI, PLUS, STAR;
 
non terminal prog;
non terminal Integer exp;
 
prog ::= exp:e
	{: System.out.println("value = " + e); :} 
	SEMI
	;
 
exp ::= NUM:n
	{: RESULT = n; :}
	| exp:e1 exp:e2 PLUS
	{: RESULT = new Integer(e1.intValue() + e2.intValue()); :} 
	| exp:e1 exp:e2 STAR
	{: RESULT = new Integer(e1.intValue() * e2.intValue()); :} 
	;

Happy

Omawiamy przykład np.

{
module Main where
import Data.Char
}
 
%name calc
%tokentype { Token }
%error { parseError }
 
%token 
      int             { TokenInt $$ }
      '+'             { TokenPlus }
      '*'             { TokenTimes }
%%
Exp : Exp Exp '+' { $1 + $2 }
    | Exp Exp '*' { $1 * $2 }
| int  { $1 }
    ;
{
 
parseError :: [Token] -> a
parseError _ = error "Parse error"
 
data Token 
      = TokenInt Int
      | TokenPlus
      | TokenTimes
 deriving Show
 
lexer :: String -> [Token]
lexer [] = []
lexer (c:cs) 
      | isSpace c = lexer cs
      | isDigit c = lexNum (c:cs)
lexer ('+':cs) = TokenPlus : lexer cs
lexer ('*':cs) = TokenTimes : lexer cs
 
lexNum cs = TokenInt (read num) : lexer rest
      where (num,rest) = span isDigit cs
 
main = getContents >>= print . calc . lexer
}

Zadania

  1. Uruchomić powyższy przykład
  2. Zmodyfikować przykład tak aby zamiast obliczać wartośc wyrażenia budował drzewo struktury i wypisywał je (np. w notacji infiksowej, albo obnawiasowanej prefiksowej.
  3. Napisać przy użyciu generatora parserów kalkulator dla notacji infiksowej (priorytety i łączność operatorów na razie rozwiązujemy przy użyciu klasycznej gramatyki
    E -> E + T  |  T ...