5

これを前置きするために、この種のものについての私の知識は貧弱です.

とにかく、CYK 構文解析アルゴリズムがどのように機能するかを独学できるように、代数式の構造を記述する文脈自由文法を開発してきました。このような構造が中置代数式だけで機能する仕組みは理解していますが、「-」演算子の単項定義と 2 項定義の両方を処理できる文法を開発する方法がわかりません。

参考までに、私が CNF で書いた文法 (S は開始記号) を次に示します。

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O -> /
O -> ^
K -> -
L -> (
R - > )

問題は、「-」演算子に遭遇したときに、CYK 解析アルゴリズムが S -> KS と A -> OS のどちらを決定するかをどのように事前に知ることができるかということです。そのような文法はもはや文脈自由ですか? そして最も重要なことは、プログラミング言語は 2 進数と単項の両方のマイナス記号を含む言語を処理できるため、これを合理的に解析するにはどうすればよいでしょうか?

4

3 に答える 3

5

これは有限状態オートマトンに関連する問題のようで、コースワークのすべてを覚えているわけではありませんが、OCaml で CYK パーサーを書いたので、先に進んで試してみます :)

3- -4たとえば、次のような式を解析しようとしている場合、S -> K Sルールで を消費して-4から、A -> O Sルールで を吸収し- -4ます。これは、最終的には最上位のSプロダクション ルールまで機能します。ただし、使用している文法には注意する必要があります。Aリストしたプロダクション ルールには到達できず、SおそらくS -> S O S何らかのルールが必要になるからです。

CYK 解析アルゴリズムが機能する方法は、質問で言及した「事前に知る」ことではなく、バックトラッキングによるものです。CYK アルゴリズムがすべきことは-4、ルールとしてを解析することです。次に、このプロダクション ルールは unary の任意の長さのチェーンを許可するため、ルールを使用して秒を再度S -> K S吸収しようとします。しかし、アルゴリズムが中間の parseでスタックしていることに気付くと、これを解析するために使用できるプロダクション シンボルがないことに気付きます。これがもはや解析可能ではないことを認識すると、戻って代わりにルールとしてを解析しようとし、陽気な方法で続行します。-S -> K S-3 S-S -> O S

これは、文法が文脈に依存しないままであることを意味します。文脈依存の文法は、生成規則の左側に端子があることを意味するため、その点では優れています。チッ！

于 2010-06-26T03:13:15.220 に答える
2

文法があいまいで、パーサーはどちらのケースを取るべきか判断できません。

おそらく、次のような文法を使用する必要があります。

S -> EXPR
EXPR -> (EXPR)
EXPR -> - EXPR
EXPR -> EXPR + EXPR
EXPR -> EXPR - EXPR
// etc...
于 2010-06-26T01:50:45.313 に答える
1

代数式に基づく文法は、あいまいさを解消するのがかなり困難です。対処する必要がある問題の例を次に示します。

a+b+c は当然 2 つの構文木を作成します。これを解決するには、+ の結合性のあいまいさを解決する必要があります。左から右への構文解析戦略にこれを任せたいと思うかもしれませんが、注意してください: べき乗はおそらく右から左に関連付ける必要があります。

a+b*c は当然 2 つの構文木を作成します。この問題を解決するには、演算子の優先順位に対処する必要があります。

暗黙の乗算 (a+bc) が許可されている場合、主にトークン化であらゆる種類の悪夢が作成されます。

あなたが言及したように、単項減算には問題があります。

これらの問題を解決したいが、代数学に特化した高速解析文法をまだ持っている場合、1 つのアプローチは、さまざまな「レベル」の EXPR を用意することです。優先順位レベルで必要なバインディングのレベルごとに 1 つずつです。例えば、

TERM -> (S)
EXPO -> TERM ^ EXPO
PROD -> PROD * EXPO
PROD -> PROD / EXPO
PROD -> -PROD
SUM -> SUM + PROD
SUM -> SUM - PROD
S -> SUM

これには、型の「昇格」も許可する必要があります: SUM -> PROD、PROD -> EXP、EXP -> TERM など。

お役に立てれば！

于 2010-06-26T04:54:02.963 に答える