問題タブ [ll]

私は文法を与え、それがLL(1). その部分はすべて問題ありませんが、後でその文法が可能かどうかを尋ねLL(k)(for k>1)られます. それを判断するには、どのような手順に従いますか?

印象はありますが、それが正しいかどうかは完全にはわかりません。文法が曖昧でない場合、First/Follow の競合が発生する可能性はありますか? 絶対に無理だとは思いますが、確認したいことがあります。

ありがとうございました。

私は文法を持っていますが、それが LL(1) にないことを証明したいと思います:

これは左再帰文法であるため、最初のセットと次のセットを見つけるために、左再帰を排除して次のようにしました。

しかし、解析テーブルに入力すると、2 つのエントリを持つセルが得られませんでした。では、与えられた文法が LL(1) にないことをどのように証明するのでしょうか?

http://hackingoff.com/compilers/ll-1-parser-generatorで次の文法を使用しています。

出力解析テーブルは

誰かが解析テーブルを説明できますか? 特に、プロダクションルールが8行しかないことを考えると、 9andの意味は何ですか10

トップダウン解析の性質上、ANTLR は、式内の葉に到達する前に、多くの余分なノードを含むいくつかの長い反復構造を持つ解析ツリーを生成します。

たとえば、次のコードでC.g4 文法 ( https://github.com/antlr/grammars-v4/tree/master/c ) を使用します。

生成されるツリーは次のとおりです。

(compilationUnit (translationUnit (externalDeclaration (functionDefinition (declarator (directDeclarator (directDeclarator main) ( )))) (compoundStatement { (blockItemList (blockItemList (blockItem (declaration (declarationSpecifiers (declarationSpecifier (typeSpecifier int)))) (initDeclaratorList (initDeclaratorList (initDeclarator (declarator ( directDeclarator a)) = (initializer (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (andExpression (equalityExpression (relationalExpression (shiftExpression (additiveExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression 5)))))))))) )))))))))) ,(initDeclarator (declarator (directDeclarator b)) = (initializer (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (andExpression (equalityExpression (relationalExpression (shiftExpression (additiveExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression 10)))))) ))))))))))))));))) (blockItem (statement (iterationStatement for ( (declaration (declarationSpecifiers (declarationSpecifier (typeSpecifier int)))) (initDeclaratorList (initDeclarator (declarator (directDeclarator i)) = (initializer (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (exclusiveOrExpression)) andExpression (equalityExpression (relationalExpression (shiftExpression (additiveExpression (additiveExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression 0))))))))))))))))) ;) (expression (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (andExpression (equalityExpression (relationalExpression (relationalExpression (shiftExpression (additiveExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression i))))))))) < (shiftExpression ( additionalExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression b)))))))))))))))) ;(expression (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (exclusiveOrExpression (andExpression (equalityExpression (relationalExpression (shiftExpression (additiveExpression (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (postfixExpression (primaryExpression i)) ++))))))))) ))))))) ) (ステートメント (compoundStatement { (blockItemList (blockItem (ステートメント (expressionStatement (expression (assignmentExpression (unaryExpression (postfixExpression (primaryExpression b))) (assignmentOperator =) (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression ( を含む) ExclusiveOrExpression (andExpression (equalityExpression (relationalExpression (shiftExpression (additiveExpression(multiplicativeExpression (castExpression (unaryExpression (unaryExpression (postfixExpression (postfixExpression (primaryExpression a)) --))))))))))))))) ;))) })))))) }))) ) )

ここで、コード スタブ "int a=5" に一致するツリーのサブ構造は次のとおりです。

(declaration (declarationSpecifiers (declarationSpecifier (typeSpecifier int))) (initDeclaratorList (initDeclaratorList (initDeclarator (declarator (directDeclarator a)) = (initializer (assignmentExpression (conditionalExpression (logicalOrExpression (logicalAndExpression (inclusiveOrExpression (exclusiveOrExpression (andExpression (relationalExpression (shiftExpression (additiveExpression) (multiplicativeExpression (castExpression (unaryExpression (postfixExpression (primaryExpression 5))))))))))))))))))))))

これはおおよそ次のように削減できることがはっきりとわかります。

(declaration (declarationSpecifiers (declarationSpecifier (typeSpecifier int))) (initDeclaratorList (initDeclaratorList (initDeclarator (declarator (directDeclarator a)) = (initializer (assignmentExpression (postfixExpression (primaryExpression 5))))))

解析ツリーを使用して特定の静的分析を実行していますが、上記の余分なノードがあるため、システムのリスナー側で多くのチェックを実行して、対象の正しいツリー ノードにアクセスする必要があります。

したがって、一連の変換ルールを使用して余分なノードを削除したり、長い反復構造を減らしたりして、解析ツリーを変更できる簡単な方法があるかどうかを知りたいです。

TA によって解決された古い試験問題に出くわしました。誰でも私を助けることができますか？

文法について作成すると、項目セットの 1 つがSLR(1)次のようになります。S--> aSb | aLR(0)

{ S-->a.Sb, S-->a., S-->.aSb, S-->.a}

上記のセットから抽出されたルールについて、どれが真ですか：

(3)が正しい理由を誰が言えるでしょうか? この質問についての詳細は？

編集: Goto は Action を参照し、goto テーブルを参照すると思います。