創造計算機等級的語言

本章作為C編譯器的第一步,會支援四則運算或其他的算術運算子以支援編譯如以下這樣的算式:

30 + (4 - 2) * -5

雖然看起來微不足道,但其實這是滿難的目標。算式有括號內的計算優先、乘除法優先等等規則,如果不想個辦法去正確解讀這些架構就沒辦法正確計算。但是,輸入的算式只是一些文字符號,這些資料並沒有包含這些架構。要正確判斷這些算式,就需要分析文字列,並好好抓出這些隱藏的架構。

這類語法分析的問題,如果沒有相關的背景知識,想要解這類的問題會相當困難。其實在以前,這類問題被認為是困難的問題,尤其在1950年代到1970年代花了非常多努力在研究,開發出了各式各樣的演算法。多虧了這些成果,在今天如果想要做語法分析,只要知道做法,是越來越簡單了。

本章將會介紹語法分析最常見演算法之一的遞迴下降分析法(recursive descendent parsing)。如 GCC 或 Clang 等大家日常所使用的 C/C++ 編譯器使用的也是遞迴下降分析法。

不僅限於編譯器,只要有解析某種結構的文本的需求而寫程式時,常常會出現這個方法。在這章所學到的方法,可以直接應用在這類問題上。本章所學的語法分析方法,說是一輩子通用的技術也不誇張吧。好好理解本章的演算法,在身為程式設計師的百寶箱中加入語法分析的招式吧。

Last updated