这是我参加更文应战的第21天，活动概况检查： 更文应战

第二章：文法和言语

1.文法方法界说–4元组（考名词解释）

（VNV_N，VTV_T，P，S）

VNV_N：非结束符集；

VTV_T：结束符集；

P：规矩(a->b的集结)–通俗点：发生式的集结；Vn，Vt，P都对错空有穷集

S：称作辨认符 或 开始符

Vn和Vt的交集为空

2. 符号串的运算

  • 联接

例如：x=ST，y=abu，则它们的联接为xy=STabu；|x|=2,|y|=3，则|xy|=5

  • 方幂

例如：x=AB，则：x0=e(标明空集)x^0=e(标明空集)，x1=ABx^1=AB，x2=ABABx^2=ABAB，x3=ABABABx^3=ABABAB

  • 集结

例如：闭包

3. 相关名词概念

  • 推导与直接推导

直接推导：v=>w

长度为n(n>=1)的推导：=>(上面+号)

长度为n(n>=0)的推导：=>(上面*号)

  • 句型

设G[S]是一个文法，假定符号串x是从辨认符号推导出来的，即有S=>x(上面*号)，则称x是文法G[S]的一个句型

  • 语句（语句⊆subseteq句型）

若x仅由结束符号组成，即S=>x，x∈XT∗xin X_T^*，则称x是G[S]的一个语句

  • 言语（用L(G)L(G)标明）

集结{x|S=>x(上面 * 号)，其间S为文法辨认符号（也就是开始符号），且x∈VT∗xin V_T^*}

简略点就是：开始符能够推出悉数语句的集结

文法描绘的言语是：该文法悉数语句的集结

4. 文法等价

假定L(G1)=L(G2)L(G1)=L(G2)，则称文法G1和G2是等价的

5. **文法的类型（首要考各种类型文法的 概念 和 对文法发生式的要求）

  • 0型文法（短语文法）

文法中的每一个发生式都是：−>alpha->beta ∈(VN∪VT)∗且至少含有一个非结束符alpha in (V_Ncup V_T)^*且至少含有一个非结束符， ∈(VN∪VT)∗beta in (V_Ncup V_T)^*

  • 1型文法（上下文有关文法）

文法中的每一个发生式都是：发生式右边长度>左边（仅S−>S->epsilon在外）

  • 2型文法（上下文无关文法）–发生式左边仅仅一个结束符

文法中的每一个发生式都是：−>alpha->beta，alpha是一个非结束符 ，∈(VN∪VT)∗beta in (V_Ncup V_T)^*

  • 3型文法（正规文法）

文法中的每一个发生式都是：A->aB或A->a，其间A和B都对错结束符，a是结束符

6. 语法树（推导树）

  • 语法树是用来描绘上下文无关文法的，语法树或许不仅有

例题：给定一文法：画出语法树、求句型、短语、句柄

7. 最左推导、标准推导（最右推导）、标准规约

  • 最左推导：a=>b，都是对a的最左非结束符进行替换，则称这样的推导为最左推导
  • 最右推导（标准推导）：对比最左推导；由标准推导得到的句型称为：标准句型（右句型）
  • 标准规约：标准推导的逆进程，也叫做最左规约（标准规约）

8. 文法的二义性

  • 假定一个文法中存在某个语句对应两棵不同的语法树，则说这个文法是二义的。

例题：例2.6、例2.8

例2.6：文法G=({E},{+，*，i，（，）}，P，E)，其间P为：

E->i

E->E+E

E->E*E

E->(E)

例2.8：文法G[E]：

E->T|E+T

T->F|T*F

F->(E)|i

存在表达式：i*i+i

假定运用例2.6的文法，则能够发生两棵不同的语法树，故例2.6的文法是二义的，而例2.8的文法不是二义的

9. 回溯界说

有一种办法是从各种或许的选择中随机选择一种，并希望它是正确的。假定以后发现它是错误的，有必要退回去，再试别的的选择，这种方法称为回溯。

10. 短语、直接短语（简略短语）、句柄（常考名词解释、大题中核算短语、直接短语、句柄…）

令G是一个文法，S是文法的开始符号，alpha beta delta 是文法G的一个句型。

  • 短语：假定有S=>Aalpha A delta (上面*号)且A=>beta (上面+号)，则称beta 是alpha beta delta 相对于A 的短语

  • 直接短语（简略短语）：A=>beta 即：直接推导出beta，则称beta 是alpha beta delta 相对于规矩A->beta 的直接短语

  • 句柄：最左直接短语（一个右句型的直接短语称为句柄，句柄的概念只适用于右句型）

短语相对于非结束符、直接短语相对于规矩

11. 有害规矩、剩下规矩

  • 有害规矩：形如U->U的发生式，它只会引起文法的二义性
  • 剩下规矩：文法中连一个语句的推导都用不到的规矩。

    • 不行抵达的：文法中某些非结束符不在任何规矩的右部出现
    • 不行停止的：文法中某些非结束符不能够从它推导出结束符号串来

12. **相关例题

12.1、容许0打头的偶正整数文法标明：

E->D|NT

T->NT|D

D->0|2|4|6|8

N->D|1|3|5|7|9

12.2、不容许0打头的偶正整数文法标明：

E->NT|D

T->FT|G

N->D|1|3|5|7|9

D->2|4|6|8

F->N|0

G->D|0

12.3、为只包括数字、加号和减号的标明式，例如：9-2+5,3-1,7等结构一个文法

E->E+T|E-T|T

T->0|1|2|…|9

12.4、经过语法树进行语法分析

编译原理温习二

  • 给出最左推导和最右推导
  • 发生式集结P或许有哪些元素
  • 给出该语句的悉数短语、简略短语、句柄

编译原理温习二