编译原理——LR(1)分析方法的分析过程

当给定LR(1)分析表(ACTION表和GOTO表), LR(1)的分析过程是这样的:

ACTION表就是标明了移进(S操作)或者规约(R操作)的表, GOTO表就是以非终结符为列, 状态为行的表

LR(1)分析过程需要三个栈, 状态栈、符号栈、剩余符号串(其实剩余符号串不需要栈的数据结构)

  1. 初始化
    • 将0状态(初始状态)加入状态栈
    • 将#符号加入符号栈
  2. 查表, 进行移进或规约操作
    • 所谓移进, 就是将剩余符号串的第一个字母加入符号栈中, 并把移进操作的状态加入状态栈(即S后的数字)
    • 所谓规约, 就是根据产生式, 把符号栈中的产生式右部替换为产生式左部
    • 步骤:
      1. 以状态栈的栈顶元素为行标, 符号栈栈顶元素为列标, 查表得到一个动作
      2. 如果动作为移进S, 则移除剩余符号串的首字母, 并将其加入符号栈; 将S后的数字加入状态栈
      3. 如果动作为规约R, 设R后的数字为n:
        • 检查第n条产生式,  将符号栈中产生式的右部替换为左部(如果产生式右部为空串, 则直接将左部加到符号栈中)
        • 平衡状态栈, 设此时符号栈中符号的个数为m, 则将状态栈中的元素个数减到m-1个
      4. 重复过程1、2、3
  3. 重复进行移进和规约, 直到规约成功(查表得到accept)或失败(查表为空)