[toc]

## 实验题目

\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}

### 要求

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

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

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

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

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

## LL (1) Parser 实现

### 功能

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

1. 计算可至空符号。
2. 计算 First 集合
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;

namespace lb_ll1parser
{
public class Production
{

/**
*
* A -> bCE
* ^    ^^^
*/
{
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;

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;

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++)
{
{
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.Rules[i].Body[j] = term;
}
else // if symbol is nonterm
{
this.Rules[i].Body[j] = this.Nonterms.First(t => t.Name == symbol.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>")
break;
}
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;
}

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
{
}
break;
}
index++;
Symbol symbol = rule.Body[index];
if (symbol is Term)
{
if (symbol.Name != ("<e>"))
{
}
break;
}
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>"))
{
}
break;
}
var nt = (Nonterm)w;
if (!IsNullable(w))
{
break;
}
}
return ret;
}
public HashSet<Term> PredictSet(int ruleIdx)
{
var rule = this.Rules[ruleIdx];
var ret = new HashSet<Term>(FirstOfBody(ruleIdx));

return ret;
}

public void ComputeParseTable()
{
this.ParseTable.Clear();
for (int i = 0; i < this.Rules.Count(); i++)
{
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;

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;

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;

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

public class Token
{

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;

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;

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;

namespace lb_ll1parser
{
public class Scanner
{
// 源代码
// 词符开始位置指针
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()
{
switch (c)
{
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()
{

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

}

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>
{
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;
return true;
}
/// <summary>
/// 从 source 扫描所有词符
/// </summary>
/// <returns></returns>
public void ScanTokens()
{
while (!isAtEnd())
{
start = current;
scanToken();
}
tokenHandler(new Token(TokenType.EOF, "", null, line));
}
}
}