软件设计师知识点整理：文法

【考法分析】

1、本知识点的主要考查方式有：给出一些概念的描述判断正误；给出一个文法的描述，判断能够识别的字符串。

【要点分析】

1、文法相关的概念：一个形式文法是一个有序四元组G=(V，T，S，P)，其中：

1）V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。

2）T：终结符。是语言的组成部分，是最终结果。 VT=

3）S：起始符。是语言的开始符号。

4）P：产生式。用终结符替代非终结符的规则。形如α→β

2、文法的分类：

注：常见的程序设计语言一般是上下文无关文法。

3、文法与语法树的推导：

例：文法G=（{a, b}, {S, A}, S, P），其中：S→aAS|a；A→SbA|SS|ba。请构造句型aabAa的推导树。

S → aAS； S → a； A → SbA；A → SS； A → ba。

【备考点拨】

1、掌握文法相关的概念和分类、对应的自动机；

2、掌握语法推导树。