1

PLYのsetlx 言語の文法は次のとおりです。

Rule 0     S' -> file_input
Rule 1     file_input -> statement_list
Rule 2     epsilon -> <empty>
Rule 3     statement_list -> statement
Rule 4     statement_list -> statement_list statement
Rule 5     statement -> simple_statement SEMICOLON
Rule 6     statement -> compound_statement
Rule 7     simple_statement -> expression_statement
Rule 8     simple_statement -> assert_statement
Rule 9     simple_statement -> assignment_statement
Rule 10    simple_statement -> augmented_assign_statement
Rule 11    simple_statement -> backtrack_statement
Rule 12    simple_statement -> break_statement
Rule 13    simple_statement -> continue_statement
Rule 14    simple_statement -> exit_statement
Rule 15    simple_statement -> return_statement
Rule 16    simple_statement -> quantor
Rule 17    simple_statement -> term
Rule 18    expression_statement -> expression
Rule 19    backtrack_statement -> BACKTRACK
Rule 20    break_statement -> BREAK
Rule 21    continue_statement -> CONTINUE
Rule 22    exit_statement -> EXIT
Rule 23    return_statement -> RETURN
Rule 24    return_statement -> RETURN expression
Rule 25    expression_list -> expression
Rule 26    expression_list -> expression_list COMMA expression
Rule 27    expression -> implication
Rule 28    expression -> lambda_definition
Rule 29    expression -> implication EQUIVALENT implication
Rule 30    expression -> implication ANTIVALENT implication
Rule 31    implication -> disjunction
Rule 32    implication -> disjunction IMPLICATES disjunction
Rule 33    disjunction -> conjunction
Rule 34    disjunction -> disjunction OR conjunction
Rule 35    conjunction -> comparison
Rule 36    conjunction -> conjunction AND comparison
Rule 37    comparison -> sum
Rule 38    comparison -> sum EQ sum
Rule 39    comparison -> sum NEQ sum
Rule 40    comparison -> sum LT sum
Rule 41    comparison -> sum LE sum
Rule 42    comparison -> sum GT sum
Rule 43    comparison -> sum GE sum
Rule 44    comparison -> sum IN sum
Rule 45    comparison -> sum NOTIN sum
Rule 46    sum -> product
Rule 47    sum -> sum PLUS product
Rule 48    sum -> sum MINUS product
Rule 49    product -> reduce
Rule 50    product -> product TIMES reduce
Rule 51    product -> product DIVIDE reduce
Rule 52    product -> product IDIVIDE reduce
Rule 53    product -> product MOD reduce
Rule 54    product -> product CARTESIAN reduce
Rule 55    reduce -> unary_expression
Rule 56    reduce -> reduce SUM unary_expression
Rule 57    reduce -> reduce PRODUCT unary_expression
Rule 58    unary_expression -> power
Rule 59    unary_expression -> SUM unary_expression
Rule 60    unary_expression -> PRODUCT unary_expression
Rule 61    unary_expression -> HASH unary_expression
Rule 62    unary_expression -> MINUS unary_expression
Rule 63    unary_expression -> AT unary_expression
Rule 64    unary_expression -> BANG unary_expression
Rule 65    power -> primary
Rule 66    power -> primary POW unary_expression
Rule 67    primary -> atom
Rule 68    primary -> attributeref
Rule 69    primary -> subscription
Rule 70    primary -> slicing
Rule 71    primary -> procedure
Rule 72    primary -> call
Rule 73    primary -> primary BANG
Rule 74    atom -> identifier
Rule 75    atom -> literal
Rule 76    atom -> enclosure
Rule 77    identifier -> IDENTIFIER
Rule 78    identifier -> UNUSED
Rule 79    attributeref -> primary DOT identifier
Rule 80    subscription -> primary LBRACKET expression RBRACKET
Rule 81    slicing -> primary LBRACKET lower_bound RANGE upper_bound RBRACKET
Rule 82    lower_bound -> expression
Rule 83    lower_bound -> epsilon
Rule 84    upper_bound -> expression
Rule 85    upper_bound -> epsilon
Rule 86    literal -> stringliteral
Rule 87    literal -> integer
Rule 88    literal -> floatnumber
Rule 89    literal -> boolean
Rule 90    stringliteral -> STRING
Rule 91    stringliteral -> LITERAL
Rule 92    integer -> INTEGER
Rule 93    floatnumber -> DOUBLE
Rule 94    boolean -> TRUE
Rule 95    boolean -> FALSE
Rule 96    enclosure -> parenth_form
Rule 97    enclosure -> set_display
Rule 98    enclosure -> list_display
Rule 99    parenth_form -> LPAREN expression RPAREN
Rule 100   set_display -> LBRACE expression RANGE expression RBRACE
Rule 101   set_display -> LBRACE expression COMMA expression RANGE expression RBRACE
Rule 102   set_display -> LPAREN argument_list RPAREN
Rule 103   list_display -> LBRACKET expression RANGE expression RBRACKET
Rule 104   list_display -> LBRACKET expression COMMA expression RANGE expression RBRACKET
Rule 105   list_display -> LBRACKET argument_list RBRACKET
Rule 106   lambda_definition -> lambda_parameters LAMBDADEF expression
Rule 107   lambda_parameters -> identifier
Rule 108   lambda_parameters -> LT parameter_list GT
Rule 109   assignment_statement -> target ASSIGN expression
Rule 110   target -> expression
Rule 111   augmented_assign_statement -> augtarget augop expression
Rule 112   augtarget -> identifier
Rule 113   augtarget -> attributeref
Rule 114   augtarget -> subscription
Rule 115   augop -> PLUS_EQUAL
Rule 116   augop -> MINUS_EQUAL
Rule 117   augop -> TIMES_EQUAL
Rule 118   augop -> DIVIDE_EQUAL
Rule 119   augop -> IDIVIDE_EQUAL
Rule 120   augop -> MOD_EQUAL
Rule 121   assert_statement -> ASSERT LPAREN expression COMMA expression RPAREN
Rule 122   term -> TERM LPAREN term_arguments RPAREN
Rule 123   term_arguments -> expression_list
Rule 124   term_arguments -> epsilon
Rule 125   procedure -> PROCEDURE LPAREN parameter_list RPAREN LBRACE block RBRACE
Rule 126   procedure -> CPROCEDURE LPAREN parameter_list RPAREN LBRACE block RBRACE
Rule 127   parameter_list -> procedure_param
Rule 128   parameter_list -> parameter_list COMMA procedure_param
Rule 129   parameter_list -> epsilon
Rule 130   procedure_param -> identifier
Rule 131   call -> primary LPAREN argument_list RPAREN
Rule 132   call -> primary LPAREN RPAREN
Rule 133   argument_list -> expression
Rule 134   argument_list -> argument_list COMMA expression
Rule 135   quantor -> FORALL LPAREN iterator_chain PIPE expression RPAREN
Rule 136   quantor -> EXISTS LPAREN iterator_chain PIPE expression RPAREN
Rule 137   iterator -> target IN expression
Rule 138   iterator_chain -> iterator
Rule 139   iterator_chain -> iterator_chain COMMA iterator
Rule 140   compound_statement -> if_statement
Rule 141   compound_statement -> switch_statement
Rule 142   compound_statement -> match_statement
Rule 143   compound_statement -> while_loop
Rule 144   compound_statement -> do_while_loop
Rule 145   compound_statement -> for_loop
Rule 146   block -> statement_list
Rule 147   block -> epsilon
Rule 148   if_statement -> IF LPAREN expression RPAREN LBRACE block RBRACE
Rule 149   if_statement -> IF LPAREN expression RPAREN LBRACE block RBRACE ELSE LBRACE block RBRACE
Rule 150   if_statement -> IF LPAREN expression RPAREN LBRACE block RBRACE ELSE if_statement
Rule 151   switch_statement -> SWITCH LBRACE case_statements default_case RBRACE
Rule 152   case_statements -> case_list
Rule 153   case_statements -> epsilon
Rule 154   case_list -> case_statement
Rule 155   case_list -> case_list case_statement
Rule 156   case_statement -> CASE expression COLON block
Rule 157   default_case -> DEFAULT COLON block
Rule 158   default_case -> epsilon
Rule 159   match_statement -> MATCH
Rule 160   while_loop -> WHILE LPAREN expression RPAREN LBRACE block RBRACE
Rule 161   do_while_loop -> DO LBRACE block RBRACE WHILE LPAREN expression RPAREN SEMICOLON
Rule 162   for_loop -> FOR LPAREN iterator_chain RPAREN LBRACE block RBRACE

最後の数メートルで、いくつかの競合が発生します。

WARNING: 
WARNING: Conflicts:
WARNING: 
WARNING: shift/reduce conflict for IN in state 34 resolved as shift
WARNING: shift/reduce conflict for COMMA in state 94 resolved as shift
WARNING: shift/reduce conflict for RPAREN in state 154 resolved as shift

新しい競合を生成せずにそれらを解決するにはどうすればよいですか? それらがどこから来たのかは理解していますが、それを修正する方法はわかりません。どんなヘルプや一般的なアドバイスも歓迎します。

4

1 に答える 1

5

これらを逆に行います。そのようにして、最も簡単なものから最も難しいものへと進むからです。実際、最初の競合の解決策は本当にありません。

3 番目の競合は、文法の実際のあいまいさの結果です。あいまいさを取り除く必要があります。

Rule 96    enclosure -> parenth_form
Rule 97    enclosure -> set_display
Rule 99    parenth_form -> LPAREN expression RPAREN
Rule 102   set_display -> LPAREN argument_list RPAREN
Rule 133   argument_list -> expression

したがって、 an を探していて、enclosure括弧で囲まれた単純な式が見つかった場合、それは a であるか、正確に 1 つの式の anでparenth_formある可能性があります。ここでの意図は、単純な括弧で囲まれた式が aになることだと思いますが、文法から判断する方法はありません.set_displayargument_listparenth_form

最も簡単な解決策は、ルール 102 に対応するAST ノードを作成するときにparenth_form、完全に削除して、要素が 1 つの場合をチェックすることです。別の可能性は、それについて明示することです。ルール 102 を変更して、 に少なくとも 2 つの式が必要になるようにします。argument_listset_displayset_display

set_display -> LPAREN expression COMMA argument_list RPAREN

ただし、ノードを構築expressionするargument_listときにを の先頭に追加する必要があるため、それでも AST を調整する必要があります。set_display

2 番目の S/R 競合は、実際には非常に似ています。次の理由で発生します。

Rule 104   list_display -> LBRACKET expression COMMA expression RANGE expression RBRACKET
Rule 105   list_display -> LBRACKET argument_list RBRACKET

そう：

LBRACKET expression COMMA expression ...

次の記号が の場合、規則 104 による削減が必要になりますRANGE。次の記号が の場合、規則 105 によりRBRACKET、また、次の記号が の場合は規則 134 によりCOMMA。(2 番目の の終わりを既に知っていると仮定しているため、これは大まかな概算expressionです。) ただし、記述されているように、文法は最初の を確認するとすぐにこれらのパスのいずれかにコミットする必要がありますCOMMA。を作成するかどうかの瞬間argument_list。

解決策は、パーサーの決定を遅らせることです。これは簡単ですが、醜いです:

list_display -> LBRACKET expression RANGE expression RBRACKET
list_display -> LBRACKET expression COMMA expression RANGE expression RBRACKET
list_display -> LBRACKET expression RBRACKET
list_display -> LBRACKET expression COMMA argument_list RBRACKET

現在、最初のCOMMAものは常にシフトされ、list_display削減するタイプの決定は 2 番目の終わりまで延期されますexpression(2 つexpressionの がある場合)。ただし、最後の 2 つのプロダクションの AST を調整してargument_list、

最初の S/R 競合が発生するINのは、 が演算子としても構文の一部としても使用されているためですiterator。

Rule 44    comparison -> sum IN sum
Rule 137   iterator -> target IN expression

しかし、targetは単なる でありexpression、expressionを派生sumさせることができるため、(ほとんどの場合) パーサーINは、解析のかなり後になるまで、何を見ているかを知ることができません。

IN演算子の優先順位を正しく適用するには、対象の型を知る必要があるため、決定を延期する前の手法はここでは機能しません。が必要なコンテキストにいてiterator、入力が次のようになっているとします。

atom1 AND atom2 IN atom3

それが反復子 (つまり、次の記号がCOMMAor RPAREN) の場合、つまり、実質的には次のようになります。

( atom1 AND atom2 ) IN atom3

ただし、それがイテレータの左側である場合は、完全に異なる方法で解析する必要があります。

( atom1 AND ( atom2 IN atom3 ) ) IN expression

さらに、atom3おそらく は任意の式である可能性がありatom3 AND atom4、2 つの解析につながります。

( atom1 AND atom2 ) IN ( atom3 AND atom4 )
( atom1 AND ( atom2 IN atom3 ) AND atom4 ) IN expression

これが、言語設計において駄洒落が悪い理由です。

LR(k)あなたの言語の特定の部分を解析できる文法はないと強く思いますが、それは直感に基づいているだけです。私には証拠がありません。ただし、実際にはあいまいではないため、GLR パーサーでは問題ありません。Python に GLR パーサー ジェネレーターがあるかどうかはわかりません。Python に縛られていない場合は、確かに を使用できますbison。

GLR パーサーは 2 番目の競合も解決しますが、これもあいまいさの結果ではありません。

于 2014-03-08T04:57:41.993 に答える