解析器和詞法分析器的設計指南？

Question

我正在寫一個詞法分析器（帶有re2c）和一個解析器（帶有檸檬），用於稍微複雜的數據格式：類似於CSV，但在特定位置使用特定的字符串類型（僅字母數字字符，字母數字字符和減號，任何字符除了引號和逗號，但帶有平衡的大括號等），大括號內的字符串和看起來像帶有可以包含參數的大括號的函數調用的字符串。

我的第一槍是一個擁有許多州的詞法分析器，每個州都遵循特定的字符串格式。但是經過許多來自詞法分析器的無用的「意外輸入」信息（它變得非常大）之後，我意識到也許它試圖完成解析器的工作。我放棄了第一次嘗試，並使用只有一個狀態的詞法分析器，許多字符標記和一個將這些標記組合成不同字符串類型的解析器。這樣做效果更好，當某些事情關閉時，我從解析器中獲得更多有用的語法錯誤，但它仍然感覺不太正確。我正在考慮向詞法分析器中添加一個或兩個狀態，但是從分析器啓動狀態，該狀態具有更好的「概述」，在給定實例中需要字符串類型。總的來說，我覺得有點愚蠢：但我可能有一個教程或書籍可以解釋什麼是詞法分析器應該（而且不應該）如何構建良好的標記模式，何時使用詞法分析器狀態，何時以及如何使用遞歸規則（使用LALR解析器），如何避免含糊不清的規則。 「Lex和YACC primer/HOWTO」雖然不錯，但還不夠，因爲我只是想解析一下數據格式，所以編譯器編譯的書籍（比如紅龍書）看起來有點超大。

或者也許有人可以在這裏給我一些簡單的規則。

Answer 1

你應該真正做的是爲你的語言寫一個語法。一旦你的，邊界很簡單：

• 詞法分析器負責把你的輸入和告訴你你有終端。
• 解析器負責將一系列終端和非終端與生產規則進行重複匹配，直到您有解析樹或解析失敗。

詞法分析器不負責除只要拒絕不可能字符，以及其它非常基本位輸入驗證。解析器完成所有工作。

看看http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html。這是一個關於解析的簡介CS課程頁面。

Answer 2

來決定，如果事情應該由解析器或詞法分析器做一個很好的試金石，是要問自己一個問題：

是否語法有任何遞歸，嵌套，自相似的元素呢？
（例如，嵌套括號，大括號，標籤，子表達式，子句等）。

如果不是，普通的正則表達式就足夠了，它可以由詞法分析器完成。
如果是，應該由解析器進行分析，因爲它至少是一個上下文無關文法。

Lexer通常用於查找您的語言的「詞彙」，並對它們進行分類（是否是名詞？動詞？一個形容詞？等等。）。
解析器用於找到正確的「句子」，如果它們是給定語言中的恰當句子，則將它們結構化。