0

我正在尝试使用 bison 和 flex 为自定义的类似 pascal 的语言制作编译器，但我最终得到了根据我的自定义语法应该正确的程序的语法错误。

我的自定义语法：

<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));
}

我的 flex 实现非常简单，我只为所需的每个符号或标识符返回标记。

在以下简单程序上使用我的实现：

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 移位/减少

任何想法都会有所帮助。谢谢！

4

1 回答 1

1

这条规则：

assignmentStat: ID ':=' expression

使用标记 ':=' 野牛给出的代码不同于任何其他标记，并且您的词法分析器无法知道，因此您几乎可以肯定不会返回它。您可能会返回ASSIGN字符序列“：=”，因此您想要：

assignmentStat: ID ASSIGN expression

对于 shift-reduce 冲突，它们意味着解析器与您指定的语言不完全匹配，而是某个子集（由默认 shift 而不是 reduce 确定）。您可以使用 bison 的-v选项在文件中获取解析器状态机（包括所有冲突）的完整打印输出.output。然后，您可以检查冲突并确定应如何更改语法以匹配您想要的。

当我在您的示例上运行 bison 时，我只看到 9 个移位/减少冲突，所有这些冲突都是由expr: expr OP expr-style 规则引起的，这些规则是模棱两可的（可能是右递归或左递归）。默认分辨率（移位）使它们都是右递归的，这可能不是您想要的。您可以将语法更改为不模棱两可，或使用 bison 的内置优先级解析工具来解决它们。

于 2013-06-17T03:45:06.510 回答