上下文无关文法

程序设计语言构造的语法可使用上下文无关文法（Context-Free Grammer）或BNF表示法来描述。文法可给出精确易懂的语法规则，可以自动构造出某些类型的文法的语法分析器，文法指出了语言的结构，有助于进一步的语义处理/代码生成，支持语言的演化和迭代。

一个上下文无关文法（CFG）包含四个部分：

• 终结符号：组成串的基本符号（词法单元的名字）

• 非终结符号：表示串的集合的语法变量，在程序设计语言中通常对应于某个程序构造，比如stmt （语句），给出了语言的层次结构，是语法分析和翻译的关键。

• 产生式：描述将终结符号和非终结符号组成串的方法

  形式：头部（左部）→体部（右部）

  头部是一个非终结符号，右部是一个符号串

  例子：expression→expression + term

• 起始符号：某个被指定的非终结符号，它对应的串的集合就是文法的语言

符号表示的规定

推导

句型/句子/语言

最左/最右推导

语法分析树

推导的图形表示形式

• 根节点的标号是文法的起始符号

• 每个叶子节点的标号是非终结符号、终结符号或空串

• 每个内部节点的标号是非终结符号

• 每个内部节点表示某个产生式的一次应用，节点的标号为产生式头，其子节点从左到右是产生式的体

树的叶子组成的序列是根的文法符号的一个句型

一颗语法分析树可对应多个推导序列，但只有唯一的最左推导及最右推导。

设计文法

词法分析和语法分析的比较

上下文无关文法比正则表达式的能力更强，所有的正则表达式都可以使用文法描述，但有一些用文法描述的语言不能用正则表达式描述。

直观的讲：有穷自动机不能无穷计数。

• 和文法相比，正则表达式更加简洁和易于理解

• 根据正则表达式自动构造的词法分析器的效率高于根据任意文法自动构造得到分析器

但没有严格的指导方针，哪些东西应该放到词法/语法规则中

• 正则最适合描述id、常量、关键字这样的语言构造的结构

• 文法最适合描述嵌套结构，如对称的括号、对应的if-then-else 等，这些无法用正则描述

文法能够描述程序设计语言的大部分语法

• 但不是全部，比如，标识符的先声明后使用则无法用上下文无关文法描述

• 因此语法分析器所接受的语言是程序设计语言的超集；必须通过语义分析来剔除一些符合文法、但不合法的程序