Introduction to parsing

发表于

Introduction to parsing

Input: sequence of tokens from lexer

Output: parse tree of the program

img

Context-Free grammars

  • 不是所有tokens都是有效的，怕parsers要进行区分

  • 程序语言是具有递归结构的

CFG包含了以下内容：

  • A set of terminals->T
  • A set of non-terminals->N
  • A start symbols->S
  • A set of productions -> X->Y1...Y2

productions可以理解成rules，例如S->(S)，意味着左边的能被右边的替代

CFG的处理过程：

  1. 从一个带有start symbol S的字符串开始
  2. 替换所有字符串中所有non-terminal X，根据production X->Y1..Y2
  3. 重复2，直到没有non-terminals

假设G是以S为start symbol的CFG，那么语言L(G)就是：

  • {a1....an | 对于所有的terminal ai，都有 S->a1....an}

terminals是不能被替换，是永恒的，terminals就是语言的tokens；

因此CFG就是指所有的production的左边只有一个非终结符

Derivations

derivations: 一些列的productions，可以表示成一颗树，根就是start symbol，箭头右边的就是子节点，

img

叶节点都是terminals，根就是start symbol。这种推导就是left-most derivation，每一步都替代掉最左边的non-terminal。

同理，也有right-most derivation：

img

right-most和left-most有着相同的parse tree。

Ambiguity

考虑grammar：E->E+E|EE|(E)|id ， string为idid+id

会解释得到两个parse tree：

img

如果有两颗以上的parse tree，我们就认为一个grammar是ambiguous。