text / xml / whatever解析を行うためのコンピュータサイエンスのテキストブックの方法
-
02-07-2019 - |
質問
しばらくの間、私の脳内でガタガタと鳴っていました。
Compilers / Flex / Bysonなどに関する調査をいくつか行いましたが、「解析スタック」やその実装方法について詳しく説明した良い参考資料を見つけることができませんでした。
誰が私が追いつくことができる良い参照を知っていますか?
編集:すべてのコンパイラー参照に感謝し、いくつかの本をリストしますが、私の主な焦点は解析後のものであり、その後の操作ではありません。
解決
これは、あなたが正しい答えとして受け入れたディマの答えへの応答です。構文解析がオートマトン理論に関連していると述べるのは悪い答えではありませんが、ここには誤解があると思います。
-
まず、有限状態オートマトンは、正規言語(たとえば、正規表現)のみを認識できます。コンテキストフリー言語を認識するためには、より強力なプッシュダウンオートマトンが必要です。オートマトンの詳細については、 http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata をご覧ください。および異なるクラスの言語との関係。
-
第二に、解析は認識とは異なります。文字列を認識することは、その文字列が文法によって生成された言語にあるかどうかだけを示します。パーサーの目的は、より難しく一般的に有用な具体的な構文ツリーを作成することです。
そこにはさまざまな解析方法がありますので、知っておくべきことを伝える特定のリファレンスを提供するのは困難です...一般に、トップダウン解析およびボトムアップ解析。ただし、興味がある場合にパーサージェネレーターで使用されるいくつかの一般的な手法の概要を次に示します。
- LR解析、 LL解析、 SLR解析 a>、 LALR解析、 GLR解析
- ANTLRの LL(*)解析
- Haskellでのモナド解析(関数型プログラミングでパーサーを構築するため)言語)
- さらにエキゾチックな式文法の構文解析
編集: この質問に再びぶつかってすみません。通常の言語と有限オートマトン、コンテキストのない言語とプッシュダウンオートマトン。この質問を見つけた人には興味深いかもしれません。