Правила грамматики бизонов для языка, подобного паскалю

Question

Я пытаюсь создать компилятор для пользовательского языка, похожего на паскаль, используя bison и flex, и в итоге получаю синтаксические ошибки для программ, которые должны быть правильными в соответствии с моей пользовательской грамматикой.

Моя пользовательская грамматика:

<program>       ::=     program id 
<block>
<block>     ::=     { 
<sequence>
}
<sequence>      ::=     <statement> ( ; <statement> )*
<brackets-seq>  ::=     { <sequence> }
<brack-or-stat> ::=     <brackets-seq> | 
<statement>
<statement>         ::=     ε |
                <assignment-stat> |
                <if-stat> |
                <while-stat> 
<assignment-stat>   ::=     id := <expression>
<if-stat>       ::=     if (<condition>) 
<brack-or-stat>
<elsepart>
<elsepart>      ::=     ε | 
else <brack-or-stat>
<while-stat>        ::=     while (<condition>) 
<brack-or-stat>
<expression>        ::=     <optional-sign> <term> ( <add-oper> <term>)* 
<term>      ::=     <factor>  (<mul-oper> <factor>)*
<factor>        ::=     constant | 
(<expression>) |  
id
<condition>     ::=     <boolterm> (and <boolterm>)*
<boolterm>      ::=     <boolfactor> (or <boolfactor>)*
<boolfactor>        ::= not [<condition>] | 
[<condition>] | 
                <expression> <relational-oper> <expression> 
<relational-oper>   ::=     == | < | > | <> | <= | >=
<add-oper>      ::=     + | -
<mul-oper>      ::=     * | /
<optional-sign>     ::=     ε | <add-oper> 

Моя грамматическая реализация на зубре:

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

%union {
    int i;
    char *s;
};

%token <i> INTEGERNUM

%token PROGRAM;
%token OR;
%token AND;
%token NOT;
%token IF;
%token ELSE;
%token WHILE;
%token PLUS;
%token MINUS;
%token MUL;
%token DIV;
%token LSB;
%token RSB;
%token LCB;
%token RCB;
%token LEFTPAR;
%token RIGHTPAR;
%token ID;
%token INT;
%token ASSIGN;
%token ISEQUAL;
%token LTHAN;
%token GTHAN;
%token NOTEQUAL;
%token LESSEQUAL;
%token GREATEREQUAL;

%left '+' '-'
%left '*' '/'

%%

program:
        PROGRAM ID block
        ;

block:
        LCB RCB
        |LCB sequence RCB
        ;

sequence:
        statement ';'sequence
        |statement ';'
        ;

bracketsSeq:
        LCB sequence RCB
        ;

brackOrStat:        
        bracketsSeq
        |statement
        ;

statement:
        assignmentStat
        |ifStat
        |whileStat
        |
        ;

assignmentStat:
        ID ':=' expression

ifStat:
        IF LEFTPAR condition RIGHTPAR brackOrStat elsepart
        ;

elsepart:
        ELSE brackOrStat
        |
        ;

whileStat:
        WHILE LEFTPAR condition RIGHTPAR brackOrStat
        ;

expression:
        addOper expression
        |expression addOper expression
        |term
        ;

term:
        term mulOper term
        |factor
        ;

factor:
        INT
        |LEFTPAR expression RIGHTPAR
        |ID
        ;

condition:
        condition AND condition
        |boolterm
        ;

boolterm:
        boolterm OR boolterm
        |boolfactor
        ;

boolfactor:
        NOT LSB condition RSB
        |LSB condition RSB
        |expression relationalOper expression
        ;

relationalOper:
        ISEQUAL
        |LTHAN
        |GTHAN
        |NOTEQUAL
        |LESSEQUAL
        |GREATEREQUAL
        ;

addOper:
        PLUS
        |MINUS
        ;

mulOper:
        MUL
        |DIV
        ;

optionalSign

        |addOper
        ;


%%

int main( int argc, char **argv )
{
             extern FILE *yyin;
             ++argv, --argc;  /* skip over program name */
             if ( argc > 0 )
                     yyin = fopen( argv[0], "r" );
             else
                     yyin = stdin;

             do
                yyparse();
            while(!feof(yyin));
}       

Моя гибкая реализация довольно проста, когда я просто возвращаю токены для каждого необходимого символа или идентификатора.

Используя мою реализацию на следующей простой программе:

program circuit
{
    a:=b;
}

Я получаю синтаксическую ошибку. В частности, когда синтаксический анализ достигает точки сразу после := в соответствии с моими отладочными отпечатками я использую:

$ ./a.exe verilog.txt
text = program
text = circuit val = circuit
text = {
text = a val = a
text = :=
syntax error

Это первый раз, когда я использую flex и bison, так что я предполагаю, что я сделал неправильную реализацию моей исходной грамматики для bison, так как после ./bison.exe -dy comp.y Я получаю команду:

конфликты бизонов 64 смещение / уменьшение

Любые идеи будут полезны. Спасибо!

Answer 1

Это правило:

assignmentStat: ID ':=' expression

использует токен ':=', который bison дает код, отличный от любого другого токена, и который ваш лексер не может узнать, поэтому вы почти наверняка не вернете его. Вы, вероятно, возвращаетесь ASSIGN для последовательности символов ':=', поэтому вы хотите:

assignmentStat: ID ASSIGN expression

Для конфликтов сдвига-уменьшения они означают, что синтаксический анализатор не точно соответствует языку, который вы указали, а скорее некоторому подмножеству (как определено смещением по умолчанию вместо сокращения). Вы можете использовать зубров -v возможность получить полную распечатку конечного автомата синтаксического анализатора (включая все конфликты) в .output файл. Затем вы можете изучить конфликты и определить, как вам следует изменить грамматику в соответствии с вашими требованиями.

Когда я запускаю Bison на вашем примере, я вижу только 9 сдвигов / уменьшений конфликтов, все из которых вытекают из expr: expr OP exprправила стиля, которые являются неоднозначными (могут быть или правыми или лево-рекурсивными). Разрешение по умолчанию (сдвиг) делает их все праворекурсивными, что может быть не тем, что вы хотите. Вы можете изменить грамматику, чтобы она не была неоднозначной, или использовать встроенные в Bison инструменты разрешения приоритетов для их разрешения.