编译原理-文法0123

文法

Posted by Kingtous on September 5, 2019

1,2,3型文法

文法 式子左边 式子右边
1型文法(上下文有关文法) 可以有多个字符,必须有一个终结符 可以有多个有限的字符
2型文法(上下文无关文法) 只能有1个非终结符 可以有多个有限的字符
3型/正规文法(正规文法) 只能有1个非终结符 1个终结符和1个非终结符 / 1个终结符

短语、直接短语、句柄

短语:语法树子树的叶子结点组成的符号串。

简单(直接)短语:语法树简单子树(子树高度为1)的叶子结点组成的符号串。

句柄:语法树的最左简单子树的叶子结点组成的符号串(即一个句型语法树的最左直接短语称为该句型的句柄)。

​ 一个句型的短语,直接短语可以有多个,但句柄只能有一个。

​ 句型本身是该句型关于开始符号的短语。

image-20190905094351187