《编译原理》课程教学资源（PPT课件讲稿）第三章 语法分析

32语言和文法 323验证文法产生的语言 G:S→(S)S|EL(O)=配对的括号串的集合 按推导步数进行归纳:推出的是配对括号串 归纳基础:S→E 归纳假设:少于n步的推导都产生配对的括号串 归纳步骤:n步的最左推导如下: S→(S)S→*(x)S→*(x)

3.2 语言和文法 3.2.3 验证文法产生的语言 G : S → (S) S |  L(G) = 配对的括号串的集合 • 按推导步数进行归纳：推出的是配对括号串 –归纳基础： S   – 归纳假设：少于n步的推导都产生配对的括号串 – 归纳步骤：n步的最左推导如下： S  (S)S * (x) S * (x) y

32语言和文法 323验证文法产生的语言 G:S→(S)S|EL(O)=配对的括号串的集合 按串长进行归纳:配对括号串可由S推出 归纳基础:S→E 归纳假设:长度小于2n的都可以从S推导出来 归纳步骤:考虑长度为2n(n≥1)的w=(x)y S→(S)S→*(x)S→*(x)

3.2 语言和文法 3.2.3 验证文法产生的语言 G : S → (S) S |  L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出 –归纳基础： S   – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n  1)的w = (x) y S  (S)S * (x) S * (x) y

32语言和文法 324适当的表达式文法 用一种层次观点看待表达式 id s id *(id+id)+id id id

3.2 语言和文法 3.2.4 适当的表达式文法 • 用一种层次观点看待表达式 id  id  (id+id) + id  id + id

32语言和文法 324适当的表达式文法 用一种层次观点看待表达式 id *id *(id+id+id * id +id id s id *lid+id) 文法 expr->expr+ term term term>term* factor l factor factor→yid|(expr)

3.2 语言和文法 3.2.4 适当的表达式文法 • 用一种层次观点看待表达式 id  id  (id+id) + id  id + id id  id  (id+id) • 文法 expr → expr + term | term term → term  factor | factor factor → id | (expr)

32语言和文法 expr>expr+ term term term->term factorI factor factor→>idl(expr) erDi erpr term expr term term factor termterm factor term k factor id Ictor actor actor id id id id id id s id 分析树 分析树

3.2 语言和文法 expr → expr + term | term term → term  factor | factor factor → id | (expr) expr id term factor id id term * term factor factor * expr expr + id factor term id id term * term factor factor id + id  id 分析树 id  id  id 分析树