程序设计语言与语言处理程序基础

[yangsirgo]

• [文法的相关概念 ]

• 文法定义： 计算机语言跟中英文一样，会有语法和规则，在计算机里叫文法。用有线的集合表示无线集合的一种工具。

• 一个形式文法是一个有序四元组，G=(V,T,S,P),其中：

1. V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符（理解成变量）。
2. T：终结符。是语言的组成部分。是最终结果。VT=
3. S：起始符。是语言的开始符号。
4. P：产生式。用终结符替换非终结符的规则，形如α→β。 **** 一个文法定义的语言是终结符号串的集合，这些终结符号串应能从文法的起始符号出发推导出来。

备注：顺序可以可能不一样，碰到选择题时看题干。有可能终结符在第二位，起始符在最后一位。

• 文法的分类

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

• 文法与语法的推导： 例题： 文法G = （{S, A},{a, b}, S, P）,其中： S → aAS|a; A → SbA|SS|ba。 请构造句型 aabAa的推导树。 解析： {S, A} 是非终结符，一般是大写的字母。 {a,b} 是终结符，一般是小写的字母。 S是起始符位置，所以从S推导。 S → aAS|a; 可以理解成 S → aAS 还可以是 S → a； A → SbA|SS|ba。 可以理解成 A → SbA 还可以是 A → SS； A → ba； 所以最终的树形结构是 ： 最终结构满足 aabAa 的树，A还可以向下推导A → ba,最终结果aabbaa

例题： 程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法Ｇ=（N，T，P，S），其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号。令集合V= N∪T，那么G所描述的语言是（ ）的集合。 B.从S出发推导出的仅包含T中符号的串 解析： 书中的话：一个文法定义的语言是终结符号串的集合，这些终结符号串应能从文法的起始符号出发推导出来。 实际意思：题干已经提到S是开始符号，所以是从S开始推导，T是终结符号，一般都是小写字母，是语言组成部分，最终结果。

[yangsirgo]

https://blog.csdn.net/qq_43439968/article/details/117136110 文法推导习题。

[yangsirgo]

27 有限自动机

[yangsirgo]

12 编译与解释