第五章LL(1)文法及其分析程序 5.1预测分析程序 5.2LL(1)文法 FIRST和FOL0W集定义和计 算 LL(1)文法定义 L(1)分析程序的生成 5.3非LL(1)文法的改造
1 第五章 LL(1)文法及其分析程序 5.1 预测分析程序 5.2 LL(1)文法 • FIRST和FOLLOW集定义和计 算 • LL(1) 文法定义 • LL(1)分析程序的生成 5.3 非LL(1)文法的改造
自上而下分析算法 要点: S→>AB A→>aA|e 由根向下构造语法树 B→>b|bB 构造最左推导 aaab 推导出的终结符是否与s 当前输入符匹配 →AB S→>AB →aAB A→>aA S aaab →aaAB A→>aA → aaaAB A→>aA → aaa e b A→>g →aaab B→>b
2 自上而下分析算法 要点： .由根向下构造语法树 .构造最左推导 .推导出的终结符是否与 当前输入符匹配 S aaab A B a A S –> AB A –> aA | B –> b | bB aaab. S AB S –> AB aAB A –> aA aaAB A –> aA aaaAB A –> aA aaa B A –> aaab B –> b
带回溯的自上而下分析 S→>AB aaabb A->aA|ε B->bbB (1)→A S→>AB aa ab b (2)→aA A→>aA (1)→A S→>AB (3)→aaA A→>aA (2)→aA. A→>aA (4)→aaaA.A->aA (3)→aaA A→>aA (5)→ aaa eb A->E 4)→aaaA..A→>aA (6)→ aaabb B->bB (5)→aaaεB..A→>E (7)→ aaabb B=>b (6)→aaab B→>b
3 带回溯的自上而下分析 S –> AB A –> aA | B –> b | bB a a a b b. S (1) A... S –> AB (2) aA... A –> aA (3) aaA... A –> aA (4) aaaA... A –> aA (5) aaa B... A –> (6) aaab B –> b aaabb. S (1) A... S –> AB (2) aA... A –> aA (3) aaA... A –> aA (4) aaaA... A –> aA (5) aaa B A –> (6’) aaa b B B –> bB (7) aaabb B –> b
预测分析程序 Predictive parser 无回测的自页向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求—一文法是L(1)的 第一个L从左到右扫描输入串 第二个L生成的是最左推导 1向前看一个输入符号( lookahead) 预测分析程序的实现技术 1递归下降子程序 2表驱动分析程序
4 预测分析程序Predictive parser 无回溯的自顶向下分析程序 特征——根据下一个输入符号为当前要处理 的非终结符选择产生式 要求——文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号（lookahead) 预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序
PL/0语言的EBNF ◆〈程序〉∴=〈分程序 ◇〈分程序〉∷三[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 ◇〈常量说明部分〉∷= CONST〈常量定义部分〉{,〈常 量定义〉}; ◇〈变量说明部分〉∷=VAR〈标识符〉{,〈标识符〉}; ◆〈过程说明部分〉∴= PROCEDURE〈标识符〉〈分程序 ;〈过程说明部分〉}; 〈语句〉∷=〈标识符〉:=〈表达式〉|IF〈条件〉 then〈语句〉|CALL|READ| BEGIN〈语句〉{;〈语 句〉}END|WILE
5 PL/0语言的EBNF ❖〈程序〉∷=〈分程序〉. ❖〈分程序〉∷=[〈常量说明部分〉][〈变量说明部 分〉][〈过程说明部分〉]〈语句〉 ❖〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常 量 定义〉}； ❖〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； ❖〈过程说明部分〉∷= PROCEDURE 〈标识符〉〈分程序〉 {；〈过程说明部分〉}； ❖〈语句〉∷= 〈标识符〉：=〈表达式〉 |IF 〈条件〉 then〈语句〉|CALL…|READ…|BEGIN 〈语句〉{；〈语 句〉} END|WHILE…|…
begin(* statemen t米) begin if sym=ident getsym then(parsing ass st *) if sym>lparen begin then error (34) getsym; else if sym=becomes repeat then getsym getsym else error(13) if sym ident expression (fsys) end then error(35) else else getsym if sym=readsym until sym>comma then if sym>paren (* parsing read st.米) then error(33) end
6 begin(*statement*) if sym=ident then (*parsing ass.st.*) begin getsym; if sym=becomes then getsym else error(13); expression(fsys); end else if sym=readsym then (* parsing read st.*) begin getsym; if sym<>lparen then error(34) else repeat getsym; if sym <> ident then error(35) else getsym until sym<>comma; if sym<>rparen then error(33); end
递归下降子程序 program - function list function list→> function function listε function - FUNC identifier( parameter list statement void Parsefunction( MatchToken(T func)i Parseldentifier(i MatchToken (T LPARen) Parseparameterlistoi MatchToken(T paren; Parsestatement oi
7 递归下降子程序 program –> function_list function_list –> function function_list | function –> FUNC identifier ( parameter_list ) statement void ParseFunction() { MatchToken(T_FUNC); ParseIdentifier(); MatchToken(T_LPAREN); ParseParameterList(); MatchToken(T_RPAREN); ParseStatement(); }
void matchToken(int expected) if (lookahead ! expected)( printf("syntax error n") exit(o)i g else / if match, consume token and move on lookahead yylex ()i
8 void MatchToken(int expected) { if (lookahead != expected) { printf("syntax error \n"); exit(0); } else // if match, consume token and move on lookahead = yylex(); }
例:递归子程序实现 表达式的语法分析 表达式的EBNF 〈表达式〉∷=[+|-]〈项〉{(+|-)〈项〉} 项〉∷=〈因子〉{(*/)〈因子〉} 〈因子〉∷= ident number`(〈表达式〉
9 例：递归子程序实现 表达式的语法分析 表达式的EBNF 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} 〈项〉∷=〈因子〉{（*|/）〈因子〉} 〈因子〉∷=ident|number|‘（’〈表达式〉 ‘）’
procedure expr egin if sym in[ plus, minus]then egin getsym; term; end else term while sym in [plus, minus] do begin getsym; term; en d end 10
10 procedure expr; begin if sym in [ plus, minus ] then begin getsym; term; end else term; while sym in [plus, minus] do begin getsym; term; end end;