ご存知のように、DFA を使用して通常の言語で文字列を検証できます。
例 1. L=ac(b)*bcb|ad(b)*bb. 文字列「acbbbcb」は、DFA によって正しいと検証できます。
また、正規言語をCFGで表現できる場合もあります。
例 2。
- S -> "a" A "b"
- A -> "c" B "c" | "d" B
- B -> "b" B | 「ば」
上記の CFG によって生成される言語は、例 1 の正規表現にすぎません。
つまり、DFA を使用して、この CFG によって生成された (通常の) 文字列を検証できます。しかし、どうすれば対応する構文木を生成できるでしょうか?