3

最近、 LALRジェネレーターを書くのに十分なほどLALRに頭を悩ませており、そのためのJavaまたはc＃スタイルの文法を構築しようとしています（その始まりはここで指定されています）。

車輪の再発明のように、パーサー ジェネレーターを作成するのは余分な労力であることはわかっていますが (なぜ Antlr を使用しないのですか?)、私の目標は、サードパーティのツールチェーンに依存せずに自分自身をコンパイルできるホビー OS をブートストラップすることです。私の問題はジェネレーターではなく、文法にあります。

ステートメントと式のあいまいさを減らす/減らすことに遭遇しています。

dangling-else などの特定の種類のあいまいさを解決する方法は知っていますが、これらのいくつかは直感的ではなく、困惑しています。

これらを解決する最善の方法は何ですか? また、ソリューションの視覚化に役立つプロトタイピング ツールはありますか? それとも、振り出しに戻って、文法用の GLR パーサー ジェネレーターを実装してみるべきでしょうか?

これらのステートメントは合法です。

Generic.List<int> myVar1 = x + 4, myVar2; // stmt -> var-decl ;
                                          // var-decl -> type-name var-decl-list

t = 99;                           // simple-stmt -> assign

i++;                              // simple-stmt -> incr-decr
                                  // incr-decr -> primary-expr ++

json.deserialize<list<int>>(obj); // simple-stmt -> call
                                  // call -> primary-expr ( params )
                                  // ...  -> primary-expr . basic-name ( params )
                                  // ...  -> basic-name . basic-name ( params )

設定方法は次のとおりです。

basic-name : ident < type-list >
           | ident

nested-name : nested-name . basic-name
            | basic-name

basic-type : int | bool | ...

type-name : nested-name
          | basic-type

stmt : var-decl ;
     | simple-stmt ;
     | ...

var-decl : type-name var-decl-list

var-decl-list : var-decl-list , var-init
              | var-init

var-init : ident assign-op expression
         | ident

simple-stmt : assign
            | call
            | incr-decr

expr : assign-expr

assign-expr : assign
            | cond-expr

assign : unary-expr assign-op expr

...
rel-expr : rel-expr < shift-expr
         ...
         | shift-expr

...
unary-expr : unary-op primary-expr
           | primary-expr

unary-op : + - ! ~ ++ --  // Prefix operators
         | ( type-name )  // Conversion operator

primary-expr : call
             | primary-expr . basic-name
             | primary-expr ++
             | ( expr )
             ...
             | basic-name

call : primary-expr ( params )

incr-decr : primary-expr ++
          | -- primary-expr
          | ...

したがって、パーサーがステートメントを予期している場合、*LR(k) アイテム セット カーネルはmethod-body -> { * stmts-opt }、状態の完全なアイテム セットは次のようになります。

method-body -> { * stmts-opt }
stmts-opt -> * stmts
stmts-opt -> *
stmts -> * stmts stmt
stmt -> * var-decl ;
stmt -> * simple-stmt ;
var-decl -> * type-name var-decl-list
simple-stmt -> * assign
simple-stmt -> * call
simple-stmt -> * incr-decr
type-name -> * nested-name
type-name -> * basic-type
nested-name -> * nested-name . basic-name
nested-name -> * basic-name
basic-name -> * ident < type-list >
basic-name -> * ident
assign -> * unary-expr assign-op expr
unary-expr -> * unary-op primary-expr
unary-expr -> * primary-expr
unary-op -> * ( typename )
unary-op -> * ! | ~ | ...
primary-expr -> * call
primary-expr -> * primary-expr . basic-name
primary-expr -> * primary-expr ++
primary-expr -> * basic-name
primary-expr -> * ( expr )
call -> * primary-expr ( params )
incr-decr -> * primary-expr ++
...

識別子がシフトされると、次の状態になります。

basic-name -> ident *
basic-name -> ident * < type-list >

これは解析または縮小され、次の状態になります。

nested-name -> basic-name *
primary-expr -> basic-name *

競合の可能性。nested-name親状態では、とにドットがあるため、先読みは役に立ちませんprimary-expr。よし、ネストされた名前で削減してみましょう:

type-name -> nested-name *
nested-name -> nested-name * . basic-name

ここには何も表示されません...では、primary-expr代わりに by を減らすのはどうですか:

unary-expr -> primary-expr *
primary-expr -> primary-expr * . basic-name
primary-expr -> primary-expr * ++
call -> primary-expr * ( params )
incr-decr -> primary-expr * ++
...

++ をシフトすると、次のようになります。

primary-expr -> primary-expr ++ *
incr-decr -> primary-expr ++ *

...別のreduce-reduce競合。

(の代わりに をシフトしてみましょうident:

primary-expr -> ( * expr )
unary-op -> ( * type-name )
expr -> * assign-expr
assign-expr -> * assign
assign-expr -> * cond-expr
assign -> * unary-expr assign-op expr
unary-expr -> * unary-op primary-expr
unary-expr -> * primary-expr
unary-op -> * ( typename )
unary-op -> * ! | ~ | ...
primary-expr -> * call
primary-expr -> * primary-expr . basic-name
primary-expr -> * primary-expr ++
primary-expr -> * basic-name
primary-expr -> * ( expr )
call -> * primary-expr ( params )
cond-expr -> * ...
...
rel-expr -> * rel-expr < shift-expr
rel-expr -> * shift-expr
...
type-name -> * nested-name
type-name -> * basic-type
nested-name -> * nested-name . basic-name
nested-name -> * basic-name
basic-name -> * ident < type-list >
basic-name -> * ident

identまたは(をスタックにシフトする場合も同じ問題が発生します。

これらは、私がこれまでに遭遇したものです。basic-nameは よりも優先されるため、 のようなものは と解釈され、実際に関係式である場合はエラーになるとrel-expr想定しています。x < nbasic-name -> ident < type-list *

私の脳は、本当に助けが必要なところまで来ました。

4

1 に答える 1

2

あなたの投稿にはいくつかの質問があるため、SO には理想的ではありません。しかし、それぞれについていくつかの考えを提供しようとします。私が見ているように、あなたには3つの問題があります：

  1. ステートメントではない式から式ステートメントを区別する。

  2. 式ステートメント内のフィールド アクセス式と競合することなく、宣言内の階層的に名前が付けられた型を解析する

  3. <比較演算子としての使用とテンプレート ブラケットとしての使用の区別。

1. ステートメントではない式から式ステートメントを区別する。

私が理解しているように、代入、インクリメントミューテーション、およびサブルーチン呼び出しなど、何らかの副作用がある (または潜在的にある) 式のみをステートメントとして許可することが望まれます。大まかに言えば、これは Java に対応し、その文法には以下が含まれます。

StatementExpression:
  Assignment
  PreIncrementExpression
  PreDecrementExpression
  PostIncrementExpression
  PostDecrementExpression
  MethodInvocation
  ClassInstanceCreationExpression

にリストされている各選択肢は、 の派生ツリーのどこかに表示StatementExpression さExpressionれ、可能性のリストから除外されています。非常に凝縮されたサンプルを次に示します。

Expression:
  LambdaExpression
  AssignmentExpression

AssignmentExpression:
  ConditionalExpression
  Assignment

Assignment:
  LeftHandSide AssignmentOperator Expression

...

UnaryExpression:
  PreIncrementExpression
  + UnaryExpression
  UnaryExpressionNotPlusMinus

PreIncrementExpression:
  ++ UnaryExpression

UnaryExpressionNotPlusMinus:
  PostfixExpression
  ~ UnaryExpression

PostfixExpression:
  Primary
  ExpressionName
  PostIncrementExpression

PostIncrementExpress:
  PostfixExpression ++

の右側で使用されているExpressionStatement非終端記号が、各優先レベルでどのように特殊なケースであるかに注意してください。どの式がステートメントになるかを制限しない C++ 文法では、個別の非終端記号は必要ありませんAssignment。

assignment-expression:
  conditional-expression
  logical-or-expression assignment-operator initializer-clause

しかし、Java では、それは機能しません。であることとであることを可能にConditionalExpressionするために、 を導出しない追加の非終端記号を作成する必要があります。AssignmentStatementAssignmentExpressionExpression

2. 式ステートメント内のフィールド アクセス式と競合することなく、宣言内の階層的に名前が付けられた型を解析する

basic-name上記と同様に、ここでは、 any (other) で始まる可能性のある他の形式のフィールドアクセス式から階層名 ( a で始まる必要があります) を配置する必要がありますprimary-expr。前者は型名または一次式にすることができます。後者は型名のみです。この区別を行うには、primary-expr生産を分割する必要があります。

primary-expr : field-access-expr
             | nested-name

non-field-access-expr:
               call
             | post-increment-expression  // was primary-expr ++
             | ( expr )
             ...

field-access-expr :
               non-field-access-expr
             | field-access-expr . basic-name

<3.を比較演算子として使用するか、テンプレート ブラケットとして使用するかを区別する。

他の 2 つの問題とは異なり、これは実際には言語のあいまいさである可能性があります。たとえば、C++ では、テンプレート ブラケットは明らかにあいまいです。特定の名前がテンプレート名であるかどうかを知る (または言われる) ことによってのみ解決できます。一方、Java では、ジェネリック名の前に型パラメーターを指定することで、あいまいさが解決されることがあります。例えば：

ConstructorDeclarator:
  [TypeParameters] SimpleTypeName ( [FormalParameterList] )

また

MethodInvocation:
  Primary . [TypeArguments] Identifier ( [ArgumentList] )

>C# には、開始に一致する可能性のあるの後の文字を調べる必要がある別のルールがあります<。このアルゴリズムは、C# マニュアルの §7.6.4.2 で説明されています。LALR（1）パーサーでそれをどのように実装するかわかりません。

于 2015-08-10T20:54:20.897 に答える