3.2语言和文法 3.2.3验证文法产生的语言 G:S→(SS|8L(G)=配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 归纳基础：S→ -归纳假设：少于步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下： S→(S)S→*(x)S→*x)J
3.2 语言和文法 3.2.3 验证文法产生的语言 G : S → (S) S | L(G) = 配对的括号串的集合 • 按推导步数进行归纳：推出的是配对括号串 –归纳基础： S – 归纳假设：少于n步的推导都产生配对的括号串 – 归纳步骤：n步的最左推导如下： S (S)S * (x) S * (x) y
3.2语言和文法 3.2.3验证文法产生的语言 G:S→(SS|8L(G)=配对的括号串的集合 按串长进行归纳：配对括号串可由S推出 -归纳基础：S→ -归纳假设：长度小于2n的都可以从S推导出来 归纳步骤：考虑长度为2n(n≥1)的w=(c)Jy S→(SS→*(x)S→*(c)Jy
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
3.2语言和文法 3.2.4适当的表达式文法 ·用一种层次观点看待表达式 idid (id+id)+idid+id
3.2 语言和文法 3.2.4 适当的表达式文法 • 用一种层次观点看待表达式 id id (id+id) + id id + id
3.2语言和文法 3.2.4适当的表达式文法 ·用一种层次观点看待表达式 id id (id+id)+id idid idid (id+id) 文法 expr→expr+term term term->term factor factor factor→id|(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)
3.2语言和文法 expr->expr+termterm term->term factor factor factor→id|(expr) expr expr expr term term factor term term factor term factor id factor id id id *id id id id idid 分析树 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 分析树