shift/reduce 冲突及如何解决

Question

我的教授分配给 me.We 的项目有问题

Goal
    ::= (Function|Statement)* <EOF>
Function
    ::= "def" Identifier "(" Argument? ")" ":" Statement 
Argument
    ::= Identifier ("=" Value )? ( "," Identifier ("=" Value )?)* 
Statement
    ::= tab* "if" Comparison ":" Statement 
    |tab* "while" Comparison ":" Statement
    |tab* "for" Identifier "in" Identifier ":" Statement
    |tab* "return" Expression 
    |tab* "print" Expression ("," Expression)* 
    |tab* Identifier ( "=" | "-=" | "/=" ) Expression 
    |tab* Identifier "[" Expression "]" "=" Expression 
    |tab* Function Call 
Expression
    ::= Expression ( "+" | "-" | "*" | "/" ) Expression
    | ( "++" | "--" ) Expression
    | Expression( "++" | "--" )
    | Identifier "[" Expression "]"
    | Function Call 
    | Value 
    | Identifier
    | "(" Expression ")"
    | "["Value ( "," Value)*"]"
Comparison
    ::= Expression ( ">" | "<" | "!=" | "==") Expression
    | "true"
    | "false"
Function Call
    ::= Identifier "(" Arglist? ")"
Arglist
    ::= Expression ( "," Expression )* 
Value
    ::= Number | "<STRING_LITERAL>"|'<STRING_LITERAL>'
Number
    ::= <INTEGER_LITERAL> 
Identifier
    ::= <IDENTIFIER>

<STRING_LITERAL> = A word that can contain letter(capitals or non capital) and white spaces
<INTEGER_LITERAL> = An integer number
<IDENTIFIER> = Name of a variable

而且我们必须用词法和句法实现一个语法文件 analysis.I 已经实现了大部分行，但我在实现其余部分时遇到了问题，因为我得到 shift/reduce conflict.My代码是这个

 Helpers
    digit = ['0' .. '9'];
    letter = ['a' .. 'z']|['A' .. 'Z']; 
    cr = 13; 
    lf = 10;
    all = [0..127]; 
    eol = lf | cr | cr lf ;
    not_eol = [all - [cr + lf]]; 

Tokens
    tab = 9;
    plus = '+';
    dplus = '++';
    minus = '-';
    dminus = '--';
    mult = '*';
    div = '/';
    eq = '=';
    minus_eq = '-=';
    div_eq = '/=';
    exclam = '!';
    l_br = '[';
    r_br = ']';
    l_par = '(';
    r_par = ')';
    comma=',';
    def = 'def';
    if = 'if';
    elif = 'elif';
    else = 'else';
    for = 'for';
    in = 'in';
    while = 'while';
    print = 'print';
    return = 'return';
    less = '<';
    great = '>';
    not_eq = '!=';
    log_eq = '==';
    true = 'true';
    semi = ':';
    false = 'false';    
    quote = '"';
    blank = (' ' | lf | cr);
    line_comment = '#' not_eol* eol; 
    number = digit+;
    id = letter (letter | digit)*;
    string = ('"'not_eol* '"' | ''' not_eol* ''');

Ignored Tokens
    blank, line_comment;
    Productions
    programme = commands*;

    commands ={stat} statement|
                 {expr}expression;

    function = {function} def id l_par argument? r_par semi statement;

    argument = {argument} id arg1? arg2*;

    arg1 = {arg1} eq value;

    arg2 = {arg2} comma id arg1?;

    statement = {if}tab* if  comparison semi statement |
                {while}tab* while comparison semi statement |
                {for}tab* for [id1]:id in [id2]:id semi statement |
                {return}tab* return expression|
                {print}tab* print expression |
                {assign}tab* id eq expression |
                {reduce_by}tab* id minus_eq expression |
                {divide_by}tab* id div_eq expression |
                {array_element_assing}tab* id l_br [ex2]:expression r_br eq [ex32]:expression;



    comparison = {true} true|
                     {false} false|
                     {lessc} [lpar]:expression less [rpar]:expression|
                     {greatc}[lpar]:expression great [rpar]:expression|
                     {equal} [lpar]:expression log_eq [rpar]:expression|
                     {not_equal} [lpar]:expression not_eq [rpar]:expression;

    expression = {multiplication} multiplication |               
                    {addition} expression plus multiplication |
                    {subtraction} expression minus multiplication |
                    {array}id l_br expression r_br;






    multiplication = {something} something |
                          {multiplication} multiplication mult something |
                          {division} multiplication div something |
                          {postfix}  suffix;

    suffix = {dplus} dplus something |
                {dminus} dminus something ;




    value = {number} number |
            {string} string;

    something ={identifier}id|
                  {numb}number|
                  {par} l_par expression r_par;

如果没有 shift/reduce 冲突，我不能包含的行是

在声明中

|tab* Function Call

在表达式中

|Expression( "++" | "--" )
| Function Call
| "["Value ( "," Value)*"]"

和行

    Function Call
    ::= Identifier "(" Arglist? ")"
Arglist
    ::= Expression ( "," Expression )*

我只发布了生产部分而不是所有内容，因为问题出在 there.I 希望得到一些帮助，了解如何在没有 shift/reduce conflict.I 的情况下将这些行添加到我的语法中现在几天来解决这个问题，看来我已经尝试 everything.Thanks 提前寻求您的帮助。

Answer 1

您的语法允许 expression 成为 command（您混淆地称为 commands）。给你的语法没有。

由于没有命令分隔符，您的语法允许连续的表达式。然而，这是模棱两可的。 a+b 是单个表达式，还是两个表达式 a 和 +b？ a(b) 呢？函数调用，或表达式 a 后跟表达式 (b)？等等。

您需要重新考虑什么是命令的决定。

顺便说一下，something 对于非终结符来说是个糟糕的名字，我觉得你把冒号称为 (:) semi 很让人困惑；分号实际上是 ;，这是我假设 semi 所指的。

shift/reduce 冲突及如何解决

shift/reduce conlfict and how to solve

compiler-construction

grammar

reduce

shift

bnf