Analiza składniowa cz. 2

Rozstrzyganie niejednoznaczności

Konflikty shift/reduce i reduce/reduce

Poniżej pokazano przykład niejednoznacznej gramatyki:

%token NUM 
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '(' expr ')'
| NUM
;

W podanej gramatyce wyrażenie:

exp - exp - exp

można wyprowadzić na dwa sposoby:

(exp - exp) - exp    -> wiązanie lewostronne
 exp - (exp - exp)   -> wiązanie prawostronne

W przypadku niejednoznaczności gramatyki podczas parsingu mogą zaistnieć dwie szczególne sytuacje:

• konfilkt shift/reduce - gdy parser staje przed wyborem dwóch poprawnych akcji: przesunięcia i redukcji,
• konflikt reduce/reduce - gdy parser ma do wyboru dwie poprawne akcje redukcji.

W obu przypadkach bison wygeneruje poprawny parser w oparciu o następujące zasady:

• konflikt shift/reduce rozstrzygany jest na korzyść operacji shift (wprowadzenie nowego symbolu ma pierwszeństwo w stosunku do zaakceptowania reguły),
• konflikt reduce/reduce rozstrzygany jest na korzyść reguły gramatycznej występującej wcześniej w specyfikacji

Bison zawsze informuje o liczbie konfliktów, które zostały automatycznie rozstrzygnięte. Zaleca się unikania konfliktów reduce/reduce.

Rozważmy inny przykład niejednoznacznej gramtyki.

instrukcja : IF_ wyrazenie instrukcja                  /* produkcja 1 */
           | IF_ wyrazenie instrukcja ELSE_ instrukcja  /* produkcja 2 */
           ;

Po wczytaniu IF_ wyrazenie instrukcja parser napotyka na konflikt shift/reduce. Ma do wyboru, albo zredukować wg produkcji 1 albo wczytać ELSE_. Ponieważ wczytanie nowego symbolu ma pierwszeństwo w stosunku do redukcji parser wczyta ELSE_ instukcja, a następnie zastosuje redukcję wg produkcji 2.

Rodzaje wiązań i priorytety

Kolejną sytuacją, która często prowadzi do konfliktów jest użycie operatorów unarnych. Ogólna postać reguły dla operatorów unarnych jest następująca:

W wielu przypadkach operatory unarne mają wyższy priorytet niż operatory binarne i ta zasada powinna znaleźć swoje odbicie w gramatyce lub podczas parsingu. Rozwiązaniem tego typu niejednoznaczności, które udostępnia bison, jest możliwość już na wstępie wyspecyfikowania priorytetu i sposobu wiązania operatorów. Priorytet i sposób wiązania dla symboli terminalnych jest określany w sekcji deklaracji. Do wyznaczenia sposobu wiązania wykorzystuje się słowa kluczowe:

%left - oznacza wiązanie lewostronne,
%right - oznacza wiązanie prawostronne,
%nonassoc - oznacza, że operator nie wiąże się ani lewostronnie,
            ani prawostronnie.

Przykład:

%nonassoc '<' '>' '=' GEQ LEQ NEQ
/* relational operators */

%left '+' '-' OR
/* addition operators */

%left '*' '/' AND
/* multiplication operators */

%right NOT UMINUS
/* unary operators */

W powyższym zapisie wszystkie symbole umieszczone w tej samej linii mają ten sam priorytet. Kolejność linii odpowiada wzrostowi priorytetu.

%left '+' '-'     /* niższy priorytet */
%left '*' '/'     /* wyższy priorytet */

Ciekawostki dot. priorytetow

Priorytet można przypisać nie tylko do terminala, ale też do reguły. Każda reguła gramatyki ma domyślnie priorytet pierwszego terminala znajdujący się po jej prawej stronie. Priorytet ten może być zmieniony przy pomocy znacznika %prec. Przy rozwiązywaniu konfliktu shift/reduce bison wybiera akcję do wykonania w następujący sposób:

• jeżeli symbol ma wyższy priorytet niż reguła wybierana jest operacja shift,
• jeżeli reguła ma wyższy priorytet niż symbol wybierana jest operacja reduce,
• jeżeli symbol i reguła mają taki sam priorytet typ wiązania symbolu determinuje rodzaj wykonywanej akcji;
  • jeżeli symbol wiąże się lewostronne wykonywana jest operacja reduce,
  • jeżeli symbol wiąże się prawostronne wykonywana jest operacja shift,
  • jeżeli dla symbolu wiązanie jest niedozwolone zgłaszany jest błąd.

Bison preferuje lewostronną rekursję w regułach gramatycznych.

Zmianę priorytetu przy pomocy znacznika %prec wykonuje się umieszczając na końcu wybranej reguły zapis %prec SYMBOL, który przypisuje całej regule priorytet tokenu SYMBOL. Przykładowo, aby nadać operatorowi unarnego minusa najwyższy priorytet można napisać:

%token NUM
%left '+' '-'
%left '*' '/'
%right UMINUS
%%
expr : expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr
| '-' expr %prec UMINUS
| '(' expr ')'
| NUM
;

Token UMINUS, nie pojawia się nigdzie na wejściu, jest wykorzystywany jedynie do nadania odpowiedniego priorytetu unaranemu minusowi. Jeżeli nie skorzystalibyśmy ze znacznika %prec w powyższej regule, oba minusy (unarny i binarny) miałyby taki sam priorytet, ponieważ są reprezentowane przez ten sam znak z wejścia ('-').

Przykłady

Poniżej pokazano przykład parsera, który działa jak prosty kalkulator. Czyta wyrażenia arytmetyczne, złożone ze stałych rzeczywistych, operatorów +, -, *, /,, minus unarnego oraz nawiasów, ze standardowego wejścia i wypisuje wyniki na standardowe wyjście. Pojedyncze litery oznaczają zmienne (nie są rozróżniane małe i duże litery). Zmienne mogą mieć przypisywane wartości w następujący sposób <zmienna> = <wyrażenie>. Przykład pochodzi z http://epaperpress.com/lexandyacc/

/* calc.y - prosty kalkulator */

%{
    #include <stdio.h>
    void yyerror(char *);
    int yylex(void);

    int sym[26];
%}

%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'

%%

program:
        program statement '\n'
        | /* NULL */
        ;

statement:
        expression                      { printf("%d\n", $1); }
        | VARIABLE '=' expression       { sym[$1] = $3; }
        ;

expression:
        INTEGER
        | VARIABLE                      { $$ = sym[$1]; }
        | expression '+' expression     { $$ = $1 + $3; }
        | expression '-' expression     { $$ = $1 - $3; }
        | expression '*' expression     { $$ = $1 * $3; }
        | expression '/' expression     { $$ = $1 / $3; }
        | '(' expression ')'            { $$ = $2; }
        ;

%%

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

int main(void) {
    yyparse();
}

Źródła:  calc.y

/* calclex.l - skaner wspolpracujacy z parserem calc.y */

%{
    #include "calc.tab.h"
    #include <stdlib.h>
    void yyerror(char *);
%}

%%

[a-z]       {
                yylval = *yytext - 'a';
                return VARIABLE;
                }

[0-9]+      {
                yylval = atoi(yytext);
                return INTEGER;
            }

[-+()=/*\n]     { return *yytext; }

[ \t]   ;       /* skip whitespace */

.               yyerror("Unknown character");

%%

int yywrap(void) {
    return 1;
}

Źródła:  calclex.l

Ćwiczenia

Ćwiczenie 1

Proszę rozszerzyć prosty kalkulator przedstawiony powyżej (calc.y) o operację potęgowania.

Ćwiczenie 2

Proszę dokończyć zadania z poprzednich zajęć.

Ćwiczenie 3

Proszę napisać parser, który rozpoznaje wąski podzbiór HTML-a, tj. znaczniki typu <HTML>, <BODY>, <B> i <BR>. Przykladowe poprawne wejscie:

<html>
<body>
Grammars for yacc are described using a variant of <b>Backus Naur Form </b>(BNF).<br> 
This technique was pioneered by John Backus and Peter Naur, and used to describe ALGOL60.<br> 
A BNF grammar can be used to express <b>context-free languages</b>.<br> 
Most constructs in modern programming languages can be represented in BNF.
</body>
</html>

Download:  test_html