程式語言入門/解析

解析

解析是將線性字元序列轉換為語法樹的問題。如今，我們在解析方面已經非常擅長。換句話說，我們擁有許多工具，例如lex和yacc，例如，可以幫助我們完成這項任務。然而，在計算機科學的早期，解析是一個非常困難的問題。這是第一個也是最基本的挑戰之一，是第一批編譯器編寫者必須面對的。所有這些都必須作為一個例子來處理。

如果程式文字描述了一個語法上有效的程式，那麼就可以將該文字轉換為語法樹。例如，下圖包含了用我們的算術表示式語法編寫的三個不同程式的不同解析樹。

有許多演算法可以從字元序列構建解析樹。有些更強大，有些更實用。基本上，這些演算法試圖找到一系列生產規則的應用序列，最終生成目標字串。例如，讓我們考慮以下語法，它指定了英語語法的非常小的子集。

<sentence> ::= <noun phrase> <verb phrase> .
<noun phrase> ::= <determiner> <noun> | <determiner> <noun> <prepositional phrase>
<verb phrase> ::= <verb> | <verb> <noun phrase> | <verb> <noun phrase> <prepositional phrase>
<prepositional phrase> ::= <preposition> <noun phrase>
<noun> ::= student | professor | book | university | lesson | programming language | glasses
<determiner> ::= a | the
<verb> ::= taught | learned | read | studied | saw
<preposition> ::= by | with | about

下面有一系列推導，表明句子“the student learned the programming language with the professor”是這種語言中一個有效的程式。

<sentence> ⇒ <noun phrase> <verb phrase> .
           ⇒ <determiner> <noun> <verb phrase> .
           ⇒ the <noun> <verb phrase> .
           ⇒ the student <verb phrase> .
           ⇒ the student <verb> <noun phrase> <prepositional phrase> .
           ⇒ the student learned <noun phrase> <prepositional phrase> .
           ⇒ the student learned <determiner> <noun> <prepositional phrase> .
           ⇒ the student learned the <noun> <prepositional phrase> .
           ⇒ the student learned the programming language <prepositional phrase> .
           ⇒ the student learned the programming language <preposition> <noun phrase> .
           ⇒ the student learned the programming language with <noun phrase> .
           ⇒ the student learned the programming language with <determiner> <noun> .
           ⇒ the student learned the programming language with the <noun> .
           ⇒ the student learned the programming language with the professor .