[toc]

实验题目

分析如下文法 $G$

$$ \begin{aligned} &\mathbf{E} \rightarrow \mathbf{E}+\mathbf{T}|\mathbf{E}-\mathbf{T}| \mathbf{T} \\ &\mathbf{T} \rightarrow \mathbf{T}^{*} \mathbf{F}|\mathbf{T} / \mathbf{F}| \mathbf{F} \\ &\mathbf{F} \rightarrow(\mathbf{E}) \mid \text { num } \end{aligned} $$

在对输入的算术表达式进行分析的过程中,依次输出所采用的产生式。

要求

方法 2:编写 LL (1) 语法分析程序,要求如下。(必做)

(1) 编程实现算法 4.2,为给定文法自动构造预测分析表。

(2) 编程实现算法 4.1,构造 LL (1) 预测分析程序。

方法 3:编写语法分析程序实现自底向上的分析,要求如下。(必做)

(1) 构造识别该文法所有活前缀的 DFA。

(2) 构造该文法的 LR 分析表。

(3) 编程实现算法 4.3,构造 LR 分析程序。

LL (1) Parser 实现

功能

  • 可以对任意文法构造分析表(Parser 生成器)
  • 可以对给定文法进行分析(四则运算 Parser)
    • 过程中输出所选的表达式

执行流程

  1. 计算可至空符号。
  2. 计算 First 集合
  3. 计算 Follow 集合
  4. 计算转移表

执行输入输出示例

PS C:\Users\i\source\repos\lb_ll1parser\lb_ll1parser\lb_ll1parser\bin\Debug\net5.0>  .\lb_ll1parser.exe
Nonterm S
  Nullable  = False
  First Set = ( num
  Follow Set = $
Nonterm E
  Nullable  = False
  First Set = ( num
  Follow Set = $ )
Nonterm E'
  Nullable  = True
  First Set = + -
  Follow Set = $ )
Nonterm T
  Nullable  = False
  First Set = ( num
  Follow Set = + - $ )
Nonterm T'
  Nullable  = True
  First Set = * /
  Follow Set = + - $ )
Nonterm F
  Nullable  = False
  First Set = ( num
  Follow Set = * / + - $ )
Nonterm S
  input (,       goto 0 (S → E $ )
  input num,     goto 0 (S → E $ )
Nonterm E
  input (,       goto 1 (E → T E' )
  input num,     goto 1 (E → T E' )
Nonterm E'
  input +,       goto 2 (E' → + T E' )
  input $,       goto 4 (E' → <e> )
  input ),       goto 4 (E' → <e> )
  input -,       goto 3 (E' → - T E' )
Nonterm T
  input (,       goto 5 (T → F T' )
  input num,     goto 5 (T → F T' )
Nonterm T'
  input *,       goto 6 (T' → * F T' )
  input +,       goto 8 (T' → <e> )
  input -,       goto 8 (T' → <e> )
  input $,       goto 8 (T' → <e> )
  input ),       goto 8 (T' → <e> )
  input /,       goto 7 (T' → / F T' )
Nonterm F
  input (,       goto 9 (F → ( E ) )
  input num,     goto 10        (F → num )
1*2+(4/5)
Top is Nonterm S
GoTo S → E $

Symbol Stack: $ E
Top is Nonterm E
GoTo E → T E'

Symbol Stack: $ E' T
Top is Nonterm T
GoTo T → F T'

Symbol Stack: $ E' T' F
Top is Nonterm F
GoTo F → num

Symbol Stack: $ E' T' num
Top is Term num, taking 1
Top is Nonterm T'
GoTo T' → * F T'

Symbol Stack: $ E' T' F *
Top is Term *, taking *
Top is Nonterm F
GoTo F → num

Symbol Stack: $ E' T' num
Top is Term num, taking 2
Top is Nonterm T'
GoTo T' → <e>

Symbol Stack: $ E' <e>
Top is Nonterm <e>, skip.
Top is Nonterm E'
GoTo E' → + T E'

Symbol Stack: $ E' T +
Top is Term +, taking +
Top is Nonterm T
GoTo T → F T'

Symbol Stack: $ E' T' F
Top is Nonterm F
GoTo F → ( E )

Symbol Stack: $ E' T' ) E (
Top is Term (, taking (
Top is Nonterm E
GoTo E → T E'

Symbol Stack: $ E' T' ) E' T
Top is Nonterm T
GoTo T → F T'

Symbol Stack: $ E' T' ) E' T' F
Top is Nonterm F
GoTo F → num

Symbol Stack: $ E' T' ) E' T' num
Top is Term num, taking 4
Top is Nonterm T'
GoTo T' → / F T'

Symbol Stack: $ E' T' ) E' T' F /
Top is Term /, taking /
Top is Nonterm F
GoTo F → num

Symbol Stack: $ E' T' ) E' T' num
Top is Term num, taking 5
Top is Nonterm T'
GoTo T' → <e>

Symbol Stack: $ E' T' ) E' <e>
Top is Nonterm <e>, skip.
Top is Nonterm E'
GoTo E' → <e>

Symbol Stack: $ E' T' ) <e>
Top is Nonterm <e>, skip.
Top is Term ), taking )
Top is Nonterm T'
Finish!

生成式定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Production
    {

        /**
        * 
        * A -> bCE
        * ^    ^^^
        * head  body
        */
        public Production(Nonterm head, List<Symbol> body)
        {
            Head = head;
            Body = body;
        }

        public Nonterm Head { get; set; }
        public List<Symbol> Body { get; set; }
        public static Production FromString(string s, string delim = "->", string bodyDelim = " ")
        {
            if (string.IsNullOrWhiteSpace(s))
            {
                throw new Exception("Empty production string.");
            }

            var spl = s.Trim().Split(delim, 2, StringSplitOptions.RemoveEmptyEntries);
            if (spl.Length != 2)
            {
                throw new Exception("Invalid production string.");
            }
            return new Production(
                new Nonterm(spl[0].Trim()),
                spl[1].Split(bodyDelim, StringSplitOptions.RemoveEmptyEntries)
                .Select(symRaw => new Symbol(symRaw.Trim())).ToList()
            );
        }
    }
}

非终结符定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Nonterm : Symbol
    {
        public Nonterm(string name) : base(name) { }
        public HashSet<Term> FirstSet;
        public HashSet<Term> FollowSet;        
        /// <summary>
        /// Nullable. Return null if not sure (not yet computed)
        /// </summary>
        public bool? Nullable;
        public override bool Equals(object obj)
        {
            var item = obj as Symbol;
            if (item == null)
            {
                return false;
            }
            return this.Name.Equals(item.Name);
        }
        public override int GetHashCode()
        {
            return this.Name.GetHashCode();
        }
    }
}

文法定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Grammar
    {
        /// <summary>
        /// Rules for Grammar. Not using a map because a Nonterm can correspond to multiple Productions 
        /// </summary>
        public List<Production> Rules;
        public HashSet<Term> Terms;


        public HashSet<Nonterm> Nonterms;
        public Dictionary<string, Term> TermsMap;

        public Dictionary<Nonterm, IDictionary<Term, int /* rule idx */ >> ParseTable;

        public Grammar(IList<Production> rules)
        {
            this.Rules = rules.ToList();
            this.ParseTable = new Dictionary<Nonterm, IDictionary<Term, int>>();
            this.InitFromRules();
        }


        public int GetStartRuleIdx()
        {
            for (int i = 0; i < this.Rules.Count; i++)
            {
                if(this.Rules[i].Head.Name == "S")
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// Initialize terms and nonterms according to production rules.
        /// </summary>
        private void InitFromRules()
        {
            this.TermsMap = new Dictionary<string, Term>();
            // init nonterms
            this.Nonterms = new HashSet<Nonterm>(this.Rules.Select(rule => new Nonterm(rule.Head.Name)));
            // init terms
            this.Terms = new HashSet<Term>();
            for (int i = 0; i < this.Rules.Count; i++)
            {
                var rule = this.Rules[i];
                for (int j = 0; j < rule.Body.Count; j++)
                {
                    var symbol = rule.Body[j];
                    // if symbol is terminal
                    if (!this.Nonterms.Contains(symbol))
                    {
                        var term = this.Terms.FirstOrDefault(t => t.Name == symbol.Name);
                        if (term == default)
                        {
                            term = new Term(symbol.Name);
                            this.Terms.Add(term);
                        }
                        this.Rules[i].Body[j] = term;
                    }
                    else // if symbol is nonterm
                    {
                        this.Rules[i].Body[j] = this.Nonterms.First(t => t.Name == symbol.Name);
                    }
                }
                this.Rules[i].Head = this.Nonterms.First(t => t.Name == this.Rules[i].Head.Name);
            }
            this.ComputeNullable();
            this.ComputeFirstSet();
            this.ComputeFollowSet();
            this.ComputeParseTable();
        }
        public void Display()
        {
            var printer = new GrammarPrinter(this);
            printer.PrintBasic();
            printer.PrintTransitionTable();
        }
        private void ComputeFollowSet()
        {
            foreach (var nt in Nonterms)
            {
                this.First(nt);
            }
        }

        private void ComputeFirstSet()
        {
            foreach (var nt in Nonterms)
            {
                this.Follow(nt);
            }
        }

        private void ComputeNullable()
        {
            foreach (var nt in Nonterms)
            {
                this.IsNullable(nt);
            }
        }

        private bool IsNullable(Symbol symbol)
        {
            if (symbol.Name == "<e>")
                return true;
            if (symbol is Term)
                return false;

            var nt = symbol as Nonterm;

            if (nt.Nullable != null)
                return (bool)nt.Nullable;

            foreach (var rule in this.Rules.Where(r => r.Head == nt))
            {
                bool allNulable = true;
                foreach (Symbol w in rule.Body)
                {
                    if (!IsNullable(w))
                    {
                        allNulable = false;
                        break;
                    }
                }
                if (allNulable)
                {
                    nt.Nullable = true;
                    return true;
                }
            }
            nt.Nullable = false;
            return false;
        }

        private HashSet<Term> First(Nonterm nt)
        {
            if (nt.FirstSet != null)
                return nt.FirstSet;
            var set = new HashSet<Term>();
            foreach (var rule in this.Rules.Where(r => r.Head == nt))
            {
                foreach (var symbol in rule.Body)
                {
                    if (symbol is Term)
                    {
                        if (symbol.Name != "<e>")
                            set.Add((Term)symbol);
                        break;
                    }
                    First((Nonterm)symbol).ToList().ForEach(x => set.Add(x));
                    if (!IsNullable(symbol))
                        break;
                }
            }
            nt.FirstSet = set;
            return set;
        }
        private List<Nonterm> openList = new List<Nonterm>();

        private HashSet<Term> Follow(Nonterm curNt)
        {
            if (curNt.FollowSet != null)
                return curNt.FollowSet;

            var ret = new HashSet<Term>();

            if (curNt.Name == ("S"))
            {
                ret.Add(new Term("$"));
                curNt.FollowSet = ret;
                return ret;
            }
            openList.Add(curNt);

            foreach (var rule in this.Rules)
            {
                int index = rule.Body.IndexOf(curNt);
                if (index == -1)
                {
                    continue;
                }

                while (index < rule.Body.Count())
                {
                    if (index == rule.Body.Count() - 1)
                    {
                        //To avoid getting stuck in the loop
                        if (!openList.Contains(rule.Head))
                        {
                            Follow(rule.Head).ToList().ForEach(r => ret.Add(r));
                        }
                        break;
                    }
                    index++;
                    Symbol symbol = rule.Body[index];
                    if (symbol is Term)
                    {
                        if (symbol.Name != ("<e>"))
                        {
                            ret.Add(symbol as Term);
                        }
                        break;
                    }
                    First((Nonterm)symbol).ToList().ForEach(r => ret.Add(r));
                    if (!IsNullable(symbol))
                    {
                        break;
                    }

                }
            }
            openList.Clear();
            curNt.FollowSet = ret;
            return ret;
        }
        private HashSet<Term> FirstOfBody(int ruleIdx)
        {
            var ret = new HashSet<Term>();

            foreach (Symbol w in this.Rules[ruleIdx].Body)
            {
                if (w is Term)
                {
                    if (!w.Name.Equals("<e>"))
                    {
                        ret.Add((Term)w);
                    }
                    break;
                }
                var nt = (Nonterm)w;
                First(nt).ToList().ForEach(r => ret.Add(r));
                if (!IsNullable(w))
                {
                    break;
                }
            }
            return ret;
        }
        public HashSet<Term> PredictSet(int ruleIdx)
        {
            var rule = this.Rules[ruleIdx];
            var ret = new HashSet<Term>(FirstOfBody(ruleIdx));
            if (IsNullable(rule.Head))
                Follow(rule.Head).ToList().ForEach(r => ret.Add(r));

            return ret;
        }

        public void ComputeParseTable()
        {
            this.ParseTable.Clear();
            for (int i = 0; i < this.Rules.Count(); i++)
            {
                Nonterm nt = this.Rules[i].Head;
                if (!this.ParseTable.ContainsKey(nt))
                {
                    this.ParseTable[nt] = new Dictionary<Term, int>();
                }
                HashSet<Term> set = this.PredictSet(i);
                foreach (Term t in set)
                {
                    this.ParseTable[nt][t] = i;
                }
            }
        }
    }
}

文法打印模块

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class GrammarPrinter
    {
        Grammar grammar;

        public GrammarPrinter(Grammar grammar)
        {
            this.grammar = grammar;
        }

        public void PrintBasic()
        {
            var g = this.grammar;
            g.Nonterms.ToList().ForEach(nt =>
            {
                Console.WriteLine($"Nonterm {nt.Name}");
                Console.WriteLine($"  Nullable  = {nt.Nullable}");
                Console.WriteLine($"  First Set = {StringifySymbolSet(nt.FirstSet)}");
                Console.WriteLine($"  Follow Set = {StringifySymbolSet(nt.FollowSet)}");
            });
        }

        private static string StringifySymbolSet<T>(ISet<T> set) where T : Symbol
        {
            var sb = new StringBuilder();
            foreach (var item in set)
            {
                sb.Append(item.Name + " ");
            }
            return sb.ToString();
        }

        public static string StringifyProduction(Production production)
        {
            var sb = new StringBuilder();
            sb.Append(production.Head.Name);
            sb.Append(" → ");
            foreach (var symbol in production.Body)
            {
                sb.Append(symbol.Name + " ");
            }
            return sb.ToString();
        }

        internal void PrintTransitionTable()
        {
            foreach (var (nt,rules) in this.grammar.ParseTable)
            {
                Console.WriteLine($"Nonterm {nt.Name}");
                foreach (var (input,ruleIdx) in rules)
                {
                    Console.WriteLine($"  input {input.Name},\t goto {ruleIdx}\t({GrammarPrinter.StringifyProduction(this.grammar.Rules[ruleIdx])})");
                }
            }
            

        }
    }
}

文法定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Grammar
    {
        /// <summary>
        /// Rules for Grammar. Not using a map because a Nonterm can correspond to multiple Productions 
        /// </summary>
        public List<Production> Rules;
        public HashSet<Term> Terms;


        public HashSet<Nonterm> Nonterms;
        public Dictionary<string, Term> TermsMap;

        public Dictionary<Nonterm, IDictionary<Term, int /* rule idx */ >> ParseTable;

        public Grammar(IList<Production> rules)
        {
            this.Rules = rules.ToList();
            this.ParseTable = new Dictionary<Nonterm, IDictionary<Term, int>>();
            this.InitFromRules();
        }


        public int GetStartRuleIdx()
        {
            for (int i = 0; i < this.Rules.Count; i++)
            {
                if(this.Rules[i].Head.Name == "S")
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// Initialize terms and nonterms according to production rules.
        /// </summary>
        private void InitFromRules()
        {
            this.TermsMap = new Dictionary<string, Term>();
            // init nonterms
            this.Nonterms = new HashSet<Nonterm>(this.Rules.Select(rule => new Nonterm(rule.Head.Name)));
            // init terms
            this.Terms = new HashSet<Term>();
            for (int i = 0; i < this.Rules.Count; i++)
            {
                var rule = this.Rules[i];
                for (int j = 0; j < rule.Body.Count; j++)
                {
                    var symbol = rule.Body[j];
                    // if symbol is terminal
                    if (!this.Nonterms.Contains(symbol))
                    {
                        var term = this.Terms.FirstOrDefault(t => t.Name == symbol.Name);
                        if (term == default)
                        {
                            term = new Term(symbol.Name);
                            this.Terms.Add(term);
                        }
                        this.Rules[i].Body[j] = term;
                    }
                    else // if symbol is nonterm
                    {
                        this.Rules[i].Body[j] = this.Nonterms.First(t => t.Name == symbol.Name);
                    }
                }
                this.Rules[i].Head = this.Nonterms.First(t => t.Name == this.Rules[i].Head.Name);
            }
            this.ComputeNullable();
            this.ComputeFirstSet();
            this.ComputeFollowSet();
            this.ComputeParseTable();
        }
        public void Display()
        {
            var printer = new GrammarPrinter(this);
            printer.PrintBasic();
            printer.PrintTransitionTable();
        }
        private void ComputeFollowSet()
        {
            foreach (var nt in Nonterms)
            {
                this.First(nt);
            }
        }

        private void ComputeFirstSet()
        {
            foreach (var nt in Nonterms)
            {
                this.Follow(nt);
            }
        }

        private void ComputeNullable()
        {
            foreach (var nt in Nonterms)
            {
                this.IsNullable(nt);
            }
        }

        private bool IsNullable(Symbol symbol)
        {
            if (symbol.Name == "<e>")
                return true;
            if (symbol is Term)
                return false;

            var nt = symbol as Nonterm;

            if (nt.Nullable != null)
                return (bool)nt.Nullable;

            foreach (var rule in this.Rules.Where(r => r.Head == nt))
            {
                bool allNulable = true;
                foreach (Symbol w in rule.Body)
                {
                    if (!IsNullable(w))
                    {
                        allNulable = false;
                        break;
                    }
                }
                if (allNulable)
                {
                    nt.Nullable = true;
                    return true;
                }
            }
            nt.Nullable = false;
            return false;
        }

        private HashSet<Term> First(Nonterm nt)
        {
            if (nt.FirstSet != null)
                return nt.FirstSet;
            var set = new HashSet<Term>();
            foreach (var rule in this.Rules.Where(r => r.Head == nt))
            {
                foreach (var symbol in rule.Body)
                {
                    if (symbol is Term)
                    {
                        if (symbol.Name != "<e>")
                            set.Add((Term)symbol);
                        break;
                    }
                    First((Nonterm)symbol).ToList().ForEach(x => set.Add(x));
                    if (!IsNullable(symbol))
                        break;
                }
            }
            nt.FirstSet = set;
            return set;
        }
        private List<Nonterm> openList = new List<Nonterm>();

        private HashSet<Term> Follow(Nonterm curNt)
        {
            if (curNt.FollowSet != null)
                return curNt.FollowSet;

            var ret = new HashSet<Term>();

            if (curNt.Name == ("S"))
            {
                ret.Add(new Term("$"));
                curNt.FollowSet = ret;
                return ret;
            }
            openList.Add(curNt);

            foreach (var rule in this.Rules)
            {
                int index = rule.Body.IndexOf(curNt);
                if (index == -1)
                {
                    continue;
                }

                while (index < rule.Body.Count())
                {
                    if (index == rule.Body.Count() - 1)
                    {
                        //To avoid getting stuck in the loop
                        if (!openList.Contains(rule.Head))
                        {
                            Follow(rule.Head).ToList().ForEach(r => ret.Add(r));
                        }
                        break;
                    }
                    index++;
                    Symbol symbol = rule.Body[index];
                    if (symbol is Term)
                    {
                        if (symbol.Name != ("<e>"))
                        {
                            ret.Add(symbol as Term);
                        }
                        break;
                    }
                    First((Nonterm)symbol).ToList().ForEach(r => ret.Add(r));
                    if (!IsNullable(symbol))
                    {
                        break;
                    }

                }
            }
            openList.Clear();
            curNt.FollowSet = ret;
            return ret;
        }
        private HashSet<Term> FirstOfBody(int ruleIdx)
        {
            var ret = new HashSet<Term>();

            foreach (Symbol w in this.Rules[ruleIdx].Body)
            {
                if (w is Term)
                {
                    if (!w.Name.Equals("<e>"))
                    {
                        ret.Add((Term)w);
                    }
                    break;
                }
                var nt = (Nonterm)w;
                First(nt).ToList().ForEach(r => ret.Add(r));
                if (!IsNullable(w))
                {
                    break;
                }
            }
            return ret;
        }
        public HashSet<Term> PredictSet(int ruleIdx)
        {
            var rule = this.Rules[ruleIdx];
            var ret = new HashSet<Term>(FirstOfBody(ruleIdx));
            if (IsNullable(rule.Head))
                Follow(rule.Head).ToList().ForEach(r => ret.Add(r));

            return ret;
        }

        public void ComputeParseTable()
        {
            this.ParseTable.Clear();
            for (int i = 0; i < this.Rules.Count(); i++)
            {
                Nonterm nt = this.Rules[i].Head;
                if (!this.ParseTable.ContainsKey(nt))
                {
                    this.ParseTable[nt] = new Dictionary<Term, int>();
                }
                HashSet<Term> set = this.PredictSet(i);
                foreach (Term t in set)
                {
                    this.ParseTable[nt][t] = i;
                }
            }
        }
    }
}

LR (1) Parser 实现

功能

  • 基于 DFA 的 LR 分析
  • 过程中输出规约所选的表达式

执行流程

  1. 人工计算分析表
  2. 利用词法分析器 Scan
  3. 根据分析表,读取输入跳转分析

分析表

$$ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|} \hline & n & + & - & * & / & ( & ) & \$ & E & F & F \\ \hline \hline 0 & \text { shift } 5 & & & & & \text { shift } 4 & & & & \\ \hline 1 & & \text { shift } 6 & \text { shift } 6 & & & & & \text { accept } & & \\ \hline 2 & & E \rightarrow T & E \rightarrow T & \text { shift } 7 & \text { shift } 7 & & E \rightarrow T & E \rightarrow T & & \\ \hline 3 & & T \rightarrow F & T \rightarrow F & T \rightarrow F & T \rightarrow F & & T \rightarrow F & T \rightarrow F & & \\ \hline 4 & \text { shift } 5 & & & & & \text { shift } 4 & & & \\ \hline 5 & & F \rightarrow \mathrm{n} & F \rightarrow \mathrm{n} & F \rightarrow \mathrm{n} & F \rightarrow \mathrm{n} & & F \rightarrow \mathrm{n} & F \rightarrow \mathrm{n} & & \\ \hline 6 & \text { shift } 5 & & & & & \text { shift } 4 & & & \\ \hline 7 & \text { shift } 5 & & & & & \text { shift } 4 & & & \\ \hline 8 & & \text { shift } 6 & \text { shift } 6 & & & & \text { shift } 11 & & \\ \hline 9 & & E \rightarrow E+T & E \rightarrow E+T & \text { shift } 7 & \text { shift } 7 & & E \rightarrow E+T & E \rightarrow E+T & \\ & & E \rightarrow E-T & E \rightarrow E-T & & & & E \rightarrow E-T & E \rightarrow E-T & \\ \hline 10 & & T \rightarrow T * F & T \rightarrow T * F & T \rightarrow T * F & T \rightarrow T * F & & T \rightarrow T * F & T \rightarrow T * F \\ & & T \rightarrow T / F & T \rightarrow T / F & T \rightarrow T / F & T \rightarrow T / F & & T \rightarrow T / F & T \rightarrow T / F & \\ \hline 11 & & F \rightarrow(E) & F \rightarrow(E) & F \rightarrow(E) & F \rightarrow(E) & & F \rightarrow(E) & F \rightarrow(E) & \\ \hline \end{array} $$

输入输出示例

1+2*3
Stack -> $                           1 + 2 \* 3 $ <- Input
Stack -> $ 1                           + 2 \* 3 $ <- Input
  Reduce by F <- n
Stack -> $ F                           + 2 \* 3 $ <- Input
  Reduce by T <- F
Stack -> $ T                           + 2 \* 3 $ <- Input
  Reduce by E <- T
Stack -> $ E                           + 2 \* 3 $ <- Input
Stack -> $ E +                           2 \* 3 $ <- Input
Stack -> $ E + 2                           \* 3 $ <- Input
  Reduce by F <- n
Stack -> $ E + F                           \* 3 $ <- Input
  Reduce by T <- F
Stack -> $ E + T                           \* 3 $ <- Input
Stack -> $ E + T \*                           3 $ <- Input
Stack -> $ E + T \* 3                           $ <- Input
  Reduce by F <- n
Stack -> $ E + T \* F                           $ <- Input
  Reduce by T <- T * F
Stack -> $ E + T                               $ <- Input
  Reduce by E <- E + T
Stack -> $ E                                   $ <- Input

词素定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_lrparser
{
    public class Lexeme
    {

        public string symbol;

        public int state;

        public double value;


        public Lexeme(string symbol, int state, object v = null)
        {
            if (v != default)
            {
                this.value = double.Parse(v.ToString());
            }
            this.symbol = symbol;
            this.state = state;
        }

        public override string ToString()
        {
            var s = this.symbol.Equals("") ? "$" : this.symbol;
            return s;
        }
    }
}

主程序

using System;

namespace lb_lrparser
{
    class Program
    {

        public static void Main()
        {
            var input = Console.ReadLine();
            //  create a string tokenizer and add all its tokens to the queue
            Action<int, string> errorHandler = (i, err) =>
            {
                Console.WriteLine("Error: " + err);
            };
            TokenHandler tokenHandler = (token) =>
            {
                if(token.Type == TokenType.EOF)
                {
                    LR1.code.Enqueue("$");
                    return;
                }
                LR1.code.Enqueue(token.Lexeme);
            };
            var scanner = new Scanner(input, errorHandler, tokenHandler);
            scanner.ScanTokens();

            //  manually push the starting state to the stack
            LR1.push(new Lexeme("", 0));
            while (!LR1.accepted)
            {
                //  determine which state we are in and jump to the method handling it
                switch (LR1.StackTop().state)
                {
                    case 0:
                    case 4:
                    case 6:
                    case 7:
                       LR1.S0();
                        break;
                    case 1:
                        LR1.S1();
                        break;
                    case 2:
                        LR1.S2();
                        break;
                    case 3:
                        LR1.S3();
                        break;
                    case 5:
                        LR1.S5();
                        break;
                    case 8:
                        LR1.S8();
                        break;
                    case 9:
                        LR1.S9();
                        break;
                    case 10:
                        LR1.S10();
                        break;
                    case 11:
                        LR1.S11();
                        break;
                }
            }

        }

    }
}

词法分析器实现

词符类型定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public enum TokenType
    {
        LeftParen, // (
        RightParen, // )
        Plus, // +
        Minus, // -
        Star, // *
        Slash, // /
        Number,
        EOF
    }
}

词符定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public delegate void TokenHandler(Token token);

    public class Token
    {
        public readonly TokenType Type;
        public readonly string Lexeme;
        public readonly object Literal;
        public readonly int Line;

        public Token(TokenType type, string lexeme, object literal, int line)
        {
            this.Type = type;
            this.Lexeme = lexeme;
            this.Literal = literal;
            this.Line = line;
        }

        public override string ToString()
        {
            return Type.ToString() + " " + Lexeme + " " + Literal;
        }
        public string Terminal()
        {
            if(this.Type == TokenType.Number)
            {
                return "num";
            }
            if(this.Type == TokenType.EOF)
            {
                return "$";
            }
            return this.Lexeme;
        }
    }
}

符号定义(基类)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Symbol
    {
        public string Name { get; set; }
        public Symbol(string name)
        {
            this.Name = name;
        }
        public override bool Equals(object obj)
        {
            var item = obj as Symbol;
            if (item == null)            {
                return false;
            }
            return this.Name.Equals(item.Name);
        }
        public override int GetHashCode()
        {
            return this.Name.GetHashCode();
        }
    }
}

终结符定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Term : Symbol
    {
        public Term(string name) : base(name) { }
        public override bool Equals(object obj)
        {
            var item = obj as Symbol;
            if (item == null)
            {
                return false;
            }
            return this.Name.Equals(item.Name);
        }
        public override int GetHashCode()
        {
            return this.Name.GetHashCode();
        }
    }
}

词法分析器实现

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lb_ll1parser
{
    public class Scanner
    {
        // 源代码
        private readonly string source;
        // 词符开始位置指针
        private int start = 0;
        // 当前位置指针
        private int current = 0;
        // 当前行指针
        private int line = 1;

        // 错误回调,参数为行号和错误信息
        private Action<int, string> errorHandler;

        private TokenHandler tokenHandler;

        public Scanner(string source, Action<int, string> errorHandler, TokenHandler tokenHandler)
        {
            this.source = source;
            this.errorHandler = errorHandler;
            this.tokenHandler = tokenHandler;
        }
        /// <summary>
        /// 扫描单个词符
        /// </summary>
        private void scanToken()
        {
            char c = Advance();
            switch (c)
            {
                case '(': addToken(TokenType.LeftParen); break;
                case ')': addToken(TokenType.RightParen); break;
                case '-': addToken(TokenType.Minus); break;
                case '+': addToken(TokenType.Plus); break;
                case '*': addToken(TokenType.Star); break;
                case '/': addToken(TokenType.Slash); break;
                case ' ':
                case '\r':
                case '\t':
                    // Ignore whitespace.
                    break;
                case '\n':
                    line++;
                    break;
                default:
                    if (IsDigit(c))
                        Number();
                    else
                        errorHandler.Invoke(line, "Unexpected character.");
                    break;
            }
        }
        /// <summary>
        /// 是否完成扫描
        /// </summary>
        /// <returns></returns>
        private bool isAtEnd()
        {
            return current >= source.Length;
        }
        /// <summary>
        /// 是否是字母或下划线
        /// </summary>
        /// <param name="c"></param>
        /// <returns></returns>
        private bool IsAlphaOrUnderline(char c)
        {
            return (c >= 'a' && c <= 'z') ||
                   (c >= 'A' && c <= 'Z') ||
                    c == '_';
        }
        /// <summary>
        /// 是否是标识符允许的字符
        /// </summary>
        /// <param name="c"></param>
        /// <returns></returns>
        private bool IsIdentifierChar(char c)
        {
            return IsAlphaOrUnderline(c) || IsDigit(c);
        }
        /// <summary>
        /// 是否是 0~9 字符
        /// </summary>
        /// <param name="c"></param>
        /// <returns></returns>
        private bool IsDigit(char c)
        {
            return c >= '0' && c <= '9';
        }
        /// <summary>
        /// 读取一个数字
        /// </summary>
        private void Number()
        {
            while (IsDigit(Peek())) Advance();

            // Look for a fractional part.
            if (Peek() == '.' && IsDigit(PeekNext()))
            {
                // Consume the "."
                Advance();

                while (IsDigit(Peek())) Advance();
            }

            addToken(TokenType.Number,
                double.Parse(source.Substring(start, current - start)));
        }
        /// <summary>
        /// 获取下个字符。如果不存在则返回 0。
        /// 无论如何指针将不会前进。
        /// </summary>
        /// <returns></returns>
        private char PeekNext()
        {
            if (current + 1 >= source.Length) return '\0';
            return source[current + 1];
        }
        /// <summary>
        /// 返回当前字符
        /// </summary>
        /// <returns></returns>
        private char Peek()
        {
            if (isAtEnd()) return '\0';
            return source[current];
        }
        /// <summary>
        /// 返回当前字符,并让指针前进 1
        /// </summary>
        /// <returns> 当前字符 </returns>
        private char Advance()
        {
            return source[current++];
        }
        /// <summary>
        /// 将 start 到 current 之间的字符作为 Token 添加到 tokens
        /// </summary>
        /// <param name="type">Token 类型 </param>
        /// <param name="literal"> 字面量 </param>
        private void addToken(TokenType type, object literal = null)
        {
            string text = source.Substring(start, current - start);
            tokenHandler(new Token(type, text, literal, line));
        }
        /// <summary>
        /// 判断当前字符是否匹配,匹配则返回 true,(若匹配)前进 1
        /// 不匹配的话指针不会前进
        /// </summary>
        /// <param name="expected"> 要比较的字符 </param>
        /// <returns> 是否匹配 </returns>
        private bool match(char expected)
        {
            if (isAtEnd()) return false;
            if (source[current] != expected) return false;
            Advance();
            return true;
        }
        /// <summary>
        /// 从 source 扫描所有词符
        /// </summary>
        /// <returns></returns>
        public void ScanTokens()
        {
            while (!isAtEnd())
            {
                start = current;
                scanToken();
            }
            tokenHandler(new Token(TokenType.EOF, "", null, line));
        }
    }
}