【从零开始学习计算机科学】编译原理（二）高级编程语言及其语法描述
- 高级语言及其语法描述
- 程序语言的定义
- 形式语言与自动机
- 文法的类型
- 语言的类型
- 自动机
- 词法规则
- 语法规则
- 四则运算的语法描述
- 布尔表达式语法描述
- 赋值、分支、循环、程序块语句语法描述
- 数组说明语句
- 过程调用语句
- 语义规则
高级语言及其语法描述
程序语言的定义
任何程序语言实现的基础是程序语言定义。程序语言的定义决定了该语言具有什么样的语言功能、什么样的数据结构、什么样的程序结构和具体的使用形式。
对于语言用户来说，语言定义就是一本用户手册；对于编译程序设计者来说，语言定义就是其编译器实现的理论依据。
形式语言与自动机
自然语言即人类讲的语言，如汉语、英语。这类语言不是人为设计而是自然进化的。而形式语言(Formal language)是用精确的数学或机器可处理的公式定义的语言。是一个字母表上的某些有限长字符串的集合，可展开交、并、补、连接、幂、闭包等数学运算。是为了特定应用而人为设计的语言，比如编程语言。
形式语言是某个字母表上，一些有限长字符串的集合。而形式文法(Formal grammar)是描述这个集合的一种方法。
一个形式文法G定义为一个四元组 ( V N , V T , P , S ) (V_N,V_T,P,S) (VN,VT,P,S)。其中 V N V_N VN是非终结符集合； V T V_T VT是终结符集合，即字母表。P是产生式规则集合，从一个字符串 α \alpha α生成另一个字符 β \beta β的规则。 S是开始符号，是一个非终结符。
形式文法描述形式语言的方法是：从开始符号S出发，不断应用产生式规则，最终能生成的所有的字符串(只有终结符号)的集合，即该形式文法所描述的形式语言。
例子，考虑如下的形式文法G，其中 V N = { S } V_N = \{S\} VN={S}， V T = { a , b } V_T = \{a, b\} VT={a,b}，S为初始符号，P包含下述产生式规则：1. S → a S S \to aS
