編譯原理第二章文法和語(yǔ)言

編譯原理第二章文法和語(yǔ)言編譯原理是一門基礎(chǔ)且重要的課程，本章節(jié)將帶你深入學(xué)習(xí)文法和語(yǔ)言的基本概念以及如何通過(guò)產(chǎn)生式來(lái)構(gòu)建編譯系統(tǒng)。什么是文法和語(yǔ)言文法語(yǔ)言的結(jié)構(gòu)規(guī)則，用于描述語(yǔ)言的語(yǔ)法范疇、語(yǔ)句的構(gòu)成方式、符號(hào)的使用方法、以及依次推導(dǎo)的過(guò)程。語(yǔ)言用于描述信息的一種形式化系統(tǒng)，可以用來(lái)傳達(dá)思想、交流觀念和傳承知識(shí)。常見(jiàn)的語(yǔ)言形式包括自然語(yǔ)言、數(shù)學(xué)語(yǔ)言等。文法的分類無(wú)限制文法產(chǎn)生式左部無(wú)限制，右部沒(méi)有限制形式的文法，允許產(chǎn)生任何形式的句子。上下文有關(guān)文法產(chǎn)生式右部可以包含左部符號(hào)，文法中上下文的內(nèi)容會(huì)影響到推導(dǎo)的結(jié)果。上下文無(wú)關(guān)文法產(chǎn)生式右部只包含一個(gè)非終結(jié)符的文法，只與左部符號(hào)相關(guān)而獨(dú)立于上下文環(huán)境的文法。正則文法只包含終結(jié)符的文法，每個(gè)產(chǎn)生式左部只有一個(gè)非終結(jié)符，右部只包含終結(jié)符和特殊符號(hào)。產(chǎn)生式和語(yǔ)言表達(dá)能力1產(chǎn)生式的定義產(chǎn)生式是一種形如A->B的符號(hào)表示法，表示將A轉(zhuǎn)換為B。2產(chǎn)生式的表示方法常見(jiàn)的產(chǎn)生式表示方法包括BNF、EBNF、ABNF等。3語(yǔ)言表達(dá)能力的判定根據(jù)某種文法產(chǎn)生的語(yǔ)言的結(jié)構(gòu)特點(diǎn)、形式能否受到識(shí)別等因素來(lái)判斷這種語(yǔ)法所具備的語(yǔ)言表達(dá)能力。文法的擴(kuò)充與簡(jiǎn)化左線性文法規(guī)則中只有產(chǎn)生式左部可以刪除，產(chǎn)生式右部只能是單個(gè)非終結(jié)符或由多個(gè)非終結(jié)符和終結(jié)符拼接而成。右線性文法規(guī)則中只有產(chǎn)生式右部可以刪除，產(chǎn)生式左部只能是單個(gè)非終結(jié)符或由多個(gè)非終結(jié)符和終結(jié)符拼接而成。等價(jià)的文法對(duì)于同一語(yǔ)言，存在多種文法，它們語(yǔ)言表達(dá)能力相同，但形式上有差別。文法的推導(dǎo)和語(yǔ)言的定義1文法的推導(dǎo)從文法的開(kāi)始符號(hào)出發(fā)，不斷使用產(chǎn)生式來(lái)替換其中的非終結(jié)符，最終得到終結(jié)符串。2文法推導(dǎo)的性質(zhì)推導(dǎo)的過(guò)程是由上至下、由左至右地進(jìn)行的。3語(yǔ)言的定義和性質(zhì)語(yǔ)言是特定文法所產(chǎn)生的所有語(yǔ)句的集合。語(yǔ)言的性質(zhì)包括可判定性、上下文無(wú)關(guān)性等。文法樹(shù)文法樹(shù)的定義表示文法符號(hào)串的一種圖形化表示，每個(gè)符號(hào)都被一棵子樹(shù)所代表。文法樹(shù)的構(gòu)造方法根據(jù)文法規(guī)則和推導(dǎo)過(guò)程構(gòu)造，文法規(guī)則的左部對(duì)應(yīng)樹(shù)的中心節(jié)點(diǎn)，右部序列對(duì)應(yīng)分支。文法樹(shù)的