基本概念

字母表$\sum$

符号串,由符号表中的符号组成的有穷序列,空串记为$\epsilon$

符号串的符号个数即为符号串长度

符号串集合,一堆符号串组成的集合.

符号串连接运算:$z = x \cdot y$

符号串方幂运算: 类似上面的连乘结果.$z = x^n$

符号串集连接运算: $C=A \cdot B = \{ x \cdot y| x \in A,y \in B \}$

符号串集方幂运算: $C=A^n$

符号串集正闭包运算: $A^{+} = A^1 \cup A^2 …$(无空串)

符号串集闭包运算: $A^{*} = A^{0} \cup A^{+}$(有空串)

规则,例如$\alpha ::= \beta$,亦可简写为$\alpha \rightarrow \beta$

文法G,即一个四元组$(V_N,V_T,P,S)$

直接推导和直接规约.

多步推导,多步归约.

句型,句子.

语言.

形式语言

语言->句子->单词->字母或单字.

词法规则,句法规则.

文法类型,规则逐渐简单,表达力逐步减弱

  • 0型文法: 短语文法
  • 1型文法: 上下文有关文法
  • 2型文法: 上下文无关文法
  • 3型文法: 正规文法

最左推导,最右推导.

规范推导

规范过程

语法二义性.

二义性文法G可能存在与之等价的无二义性文法.

存在先天性二义性语言.

文法的二义性判定问题是不可解的,不存在这个判定问题的算法.

句型分析.

推导法:自上而下的分析方法

规约法:自下而上的分析方法

课后作业

  1. 文法G=（{A, B, S}，{a,b,c},P,S）,

其中P为

S–>Ac|aB

A–>ab

B–>bc

写出L(G[S])的全部.

答:
$\{ abc\}$

  1. 文法G[N]为

N–>D|ND

D–>0|1|2|3|4|5|6|7|8|9|

G[N]的语言是什么

答:所有自然数

  1. 证明文法G=（{E,O},{(,),+,*,v,d},P,E）是二义的，其中P为

E–>EOE|(E)|v|d

O–>+|*

答: v+v*v有两种推到方式,如下图所示

赏

我很好奇