语言和语义

1.1 暴力搜索

为了证明语言的语义，我们的目标是证明表达式的步骤。但我们不确定它的步骤是什么，或者应用什么规则。这里的证明策略相当简单：暴力搜索。

所谓暴力搜索，就像它的名字，解决问题的简单方法依赖于纯粹的计算能力，并尝试各种可能性，而不是先进的特定的技术来提高效率。

暴力搜索也称之为穷举搜索，也称为生成和测试，是一种非常通用的问题解决技术和算法范式，它包括系统地枚举解决方案的所有可能候选者并检查每个候选者是否满足问题的陈述。

有四个可能的规则可能适用于我们的术语。我们可以依次查看每个以决定哪个适用。

D-Num：表达式不是数字，因此 D-Num 不适用。

D-left：如果可以步，则适用此规则。 
因此 D-Left 不适用。e1e1=1e1val

D-⊕：如果两者都是数字，则此规则适用。 
不是数字，因此 D-⊕ 不适用。e1e2e2

D-Right：此规则适用于 if 是一个值（它是），并且 if 可以步进。
这似乎可能适用，因此我们可以从这里开始证明。

在算术中，组合由将两个数字组合在一起的二元运算符组成。我们可以将算术的结构写成上下文无关的语法.

对计算作为语义的概念更感兴趣。例如，我们的目标不是为字符串分配语义，而是由程序员决定如何在给定应用程序中解释字符串的内容。

相反，程序是一种可以计算的结构，更一般地说，给定一种定义表达式的语言，我们的目标是定义一种语义，可以将表达式简化为原始形式.

1.2 语法树

在讨论结构时，我们必须小心，以了解我们语言的真实形状。

当用文本传达时，算术表达式看起来像一个连续的字符串，
例如1 +2∗3，但这只是文本作为媒介的限制。

上下文无关语法描述树结构，线性文本隐式描述此树：

		+
	     1     *
	         2  3

从这个角度来看，我们可以将语法定义为建立语言的基本结构。

语法不仅仅是关于大括号与空格或vs.这有时被区分为语言的抽象语法与其具体语法，其中抽象是指结构，具体是指符号。

对于相同的抽象语法，一种语言可以有多个具体的语法，例如我们的算术图和文本表示。对应于一段语法的树随后称为抽象语法树或 AST。

树和上下文无关语法通常被视为编程语言的基础。
但这是一个有趣且开放的问题，即语言语法的替代表示。

关于语法树还有大量文章和书籍值得阅读。

1.2 优先级

面对模棱两可的语法，将字符串解析为树的任务通常没有被充分指定。
在我们的语法中，字符串1 + 2 / 3 可以解析为(1 + 2) / 3或1 + (2 / 3).

仔细设计明确的语法是编译器实现者的一项重要任务。

小结

我们在讨论语法时主要关注的是理解语言结构的最简单本质。

因此，我们不会试图使语法更复杂以避免歧义，相反，我们将（用自然语言）声明优先级和结合性规则。
对于算术，您可以采用标准关联性和优先级 （PEMDAS） 规则。

一般来说，谈论语言可能很困难，因为我们必须使用语言来传达语言的本质概念。
我们可以特别强调一些细节，以澄清某些区别，比如使用 +^ 表示通常使用的+。

但是在这里，我们使用算术运算符与+，−，∗，/ 符号及其在标准算术中是相同关联的语义。