不会在论坛这种页面里编辑上下标，请见谅。
（一）概念
1.文法：描述语言语法结构的规则，抽象定义程序设计语言包含的字符串，
文法G是一个四元组： G=($V_N$,$V_T$,P,S)
2.$V_N$是非终结符集合，非终结符有：
大写字母S，通常表示开始符号；
大写字母，如：A，B，C；
代表程序构造的大写字母，如：E（表达式），T（项），F（因子）。
非终结符可推出非终结符或终结符，可理解为用非终结符代表“非终结符+终结符”这个字符串，因此非终结符是缩写代替，不是语言的组成部分，不是最终结果。
3.$V_T$是终结符集合，终结符有：
小写字母，如：a，b，c；
运算符，如：+，*；
标点符号，如：括号，逗号；
数字0，1，...，9。
终结符是语言的组成部分，是最终结果。
$V_N$∩$V_T$=Ø
4.令V=$V_N$∪$V_T$，V为文法G的词汇表，V中的符号称为文法符号。
5.P是产生式集合，每个产生式是形如“α→β”的规则，即产生式是用终结符替代非终结符的规则（或非终结符推出终结符的规则），
其中α称为产生式的左部，α∈$V^+$且α中至少含有一个非终结符；β称为产生式的右部且β∈$V^*$。
即左部不为空&&至少含有一个非终结符，右部可为空、非终结符、终结符的组合。
文法中，一个字母或一个数字或一个符号等都当做一个字符，$a^3$表示aaa。
正则闭包：除空集外所有幂集，$A^+$=$A^1$∪$A^2$∪$A^3$∪...∪$A^n$
闭包：$A^*$=$A^0$∪$A^+$，$A^0$={ε}，ε空集。
如：a={a,aa,aaa,...,ε}，(ab)={ab,abab,ababab,...,ε}。
若干个产生式α→$β_1$，α→$β_2$，...，α→$β_n$的左部相同时，可简写为α→$β_1$|$β_2$|...|$β_n$，称$β_i$（1<=i<=n）为α的一个候选式。
6.S是语言的开始符号，S∈$V_N$，它至少要在一条产生式中作为左部出现。
文法是从开始符号S，用产生式P，到终结符$V_T$得到的内容（语言字符串）。
7.例：给出产出语言为｛$a^n$$b^n$|n是大于等于1的整数｝的文法。
解： 蕴含条件：a，b每次出现的数量相同，且向左、右两边递增。
G(S)： S→ab
S→aSb
（二）分类
乔姆斯基（Chomsky）把文法分成4种类型，4种类型都是G=($V_N$,$V_T$,P,S)的形式，0型到3型对产生式P的限制越来越大，文法描述能力越来越小（0型最大）：
常见程序设计语言是2型上下文无关文法。
（三）推导
推导：对于2型上下文无关文法（左部必须是非终结符），从开始符号S出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列，直到产生一个终结符的序列为止。
语法树(derivational tree，推导树)是用来描述上下文无关文法的句型推导的直观工具，一颗语法树应同时具有以下特征：
①每个结点都有一个标记，此标记是V中的一个文法符号；//每个结点要么是非终结符，要么是终结符。
②根的标记是S；//推导是从根S开始的。
③标记为A的结点至少有一个除它自己外的子孙，则A肯定在$V_N$中；//有子孙说明能推导出其他结点，根据2型定义A∈$V_N$。
④标记为A的结点的直接孩子从左到右的标记分别是$A_1$,$A_2$,...,$A_k$，那么A→$A_1$$A_2$...$A_k$一定是P中的一个产生式。//父结点推导出子结点的标记序列。
发表于 2024-4-4 11:16
|
发表于 2024-4-4 12:12
发表于 2024-4-4 12:31
