编程语言入门/解析

解析

解析是将线性字符序列转换为语法树的问题。如今，我们在解析方面已经非常擅长。换句话说，我们拥有许多工具，例如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 .