0

これを行うための標準的な方法があると確信していますが、どこから検索を開始すればよいのかさえわかりません。

どの言語でも、たとえば次の形式の構造（文法）をどのように認識できますか？

Exp ::= Number |(Exp) | Exp + Exp 
Number ::= Number Digit | Digit
Digit ::= 0 | ... | 9

つまり、のような文字列が与えられた32 + (43 + 23)場合、それが合法であるかどうかをどのように判断できますか？標準的なアルゴリズムか何かがありますか？何を検索すればいいのかわからないので、このサイトも検索できませんでした。

4

1 に答える 1

1

解析アルゴリズム (メンバーシップ アルゴリズム) を探しています。構文解析は、形式言語で言語記号の文字列を分析するプロセスです。そして、はい、任意の文脈自由文法に対して可能な構文解析アルゴリズムがあります。これは基本的なアルゴリズムですが非効率的なブルート フォースです。句構造構文解析と同様に、最悪の場合の複雑さは O(n 3 )ですここで) REFF1 . しかし、文法が標準 (制限された) 形式であれば、より効率的なアルゴリズムが可能です。LL パーサーや LR パーサーなど、さまざまな解析アルゴリズムがあります。参照

于 2012-12-28T15:51:05.183 に答える