3.2语言和文法 3.2.3验证文法产生的语言 G:S→(S)S|8L(G)=配对的括号串的集合 按推导步数进行归纳：推出的是配对括号串 -归纳基础：S→ -归纳假设：少于步的推导都产生配对的括号串 -归纳步骤：步的最左推导如下： S→(S)S→*x)S→*(c)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→(S)S|8L(G)=配对的括号串的集合 按串长进行归纳：配对括号串可由S推出 -归纳基础：S→ -归纳假设：长度小于2的都可以从S推导出来 -归纳步骤：考虑长度为2n(n≥1)的w=(c)J S→(S)S→*(x)S→*(x)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适当的表达式文法 ·用一种层次观点看待表达式 id id (id+id)+id id id 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+term term term->term factor factor factor-→id|(expr) expr expr term expr term term factor term factor term factor id id ididid id id +idid a 分析树 id 分析树
3 2. 语言和文法 expr expr + term | term term term factor | factor factor id | (expr) expr expr term term factor expr + term id term factor * term factor * term * term f t factor id id * term factor factor factor id id factor id id id id + id id id id f id id id + id id 分析树 id id id 分析树
3.2语言和文法 3.2.5消除二义性 stmt→if expr then stmt if expr then stmt else stmt other ,句型：if expr then if expr then stmt else stmt 两个最左推导： stmt =if expr then stmt -if expr then if expr then stmt else stmt stmt =if expr then stmt else stmt >if expr then if expr then stmt else stmt
3 2. 语言和文法 3.2.5 消除二义性 stmt if expr then stmt | if expr then stmt else stmt | other • 句型：if expr then if then if expr then stmt else stmt • 两个最左推导： stmt if expr then stmt if expr then if expr then stmt else stmt stmt if expr then stmt else stmt if expr then if expr then stmt else stmt