编译原理（第3版）.pdf

文法

描述语言的语法结构的形式规则
<句子> => <主语><谓语><间接宾语><直接宾语>

语法描述的概念

  • 字母表：一个有穷的字符集，记为∑
  • ∑上的字（也叫字符串）由∑中字符所构成的一个有穷序列
  • 字母表的每个元素称为字符
  • 不包含任何字符的序列称为空字，记为ε
  • 用∑*表示∑中所有字的全体，包含空字ε
    • ∑*的子集U和V的连接（积）的定义UV
    • V自身的n次积记为Vn=VV…V（n个）
    • V={ε}
    • V是V的闭包：V=V ∪V∪V∪V∪…
    • V是V的正规规闭包：V=VV*

上下文无关文法

G是一个四元组 G=(VVS，P)

  • VT终结符
  • VN非终结符
  • S文法的开始符号
  • P产生式集合（有限）

第一次作业

image.png
image.png
image.png

文法和语言联系

image.png

短语、直接短语、句柄

image.png

image.pngimage.png

image.png

语法树

image.png
image.pngimage.png

文法的二义性

image.png
image.png

二义性的消除

image.png
2.构造等价无二义性的文法

文法和语言的分类

image.png
image.png
image.png
image.png
image.png
image.png
image.pngimage.png