C# 文法分析器代码：LL(1) 语法分析实现
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;
namespace byyljxfzxt
{
public partial class Form4 : Form
{
public Form4()
{
InitializeComponent();
}
//--------------------预处理
Dictionary<string, List<string>> production;
Dictionary<string, List<string>> firsts;
Dictionary<string, List<string>> follows;
Dictionary<string, List<string>> selects;
Dictionary<string, Dictionary<string, string>> table;
List<string> terminals;
List<string> nonterminals;
private void button4_Click(object sender, EventArgs e)
{
string text = richTextBox1.Text;
production = new Dictionary<string, List<string>>();
string[] pro = text.Split('\n');
foreach (string s in pro)
{
if (s == "") continue;
Regex.Replace(s, " ", "");
string[] ga = Regex.Split(s, "->");
if (ga.Length != 2) return;
if (ga[0].Length == 0 || ga[1].Length == 0)
return;
if (ga[0].Length != 1 || !char.IsUpper(ga[0][0])) return;
string[] ga2 = Regex.Split(ga[1], "\|");
if (!production.ContainsKey(ga[0]))
production.Add(ga[0], new List<string>());
foreach (string s1 in ga2)
production[ga[0]].Add(s1);
}
firsts = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFirst(item, production, firsts);
follows = new Dictionary<string, List<string>>();
foreach (var item in production.Keys)
GetFollow(item, production, firsts, follows);
if (JudgeLL1(production, firsts, follows))
{
MessageBox.Show("该文法是LL(1)文法\n");
}
else
{
MessageBox.Show("该文法不是LL(1)文法，存在左递归或者存在FIRST集合有交集的情况！\n");
}
button1.Enabled = true;
button2.Enabled = true;
button6.Enabled = true;
}
private void GetFirst(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1)
{
// 如果该非终结符的 FIRST 集已经被计算出，则直接返回
if (firsts1.ContainsKey(symbol))
{
return;
}
firsts1.Add(symbol, new List<string>());
// 遍历产生式，计算 FIRST 集
foreach (var prod in production1[symbol])
{
// 如果产生式首字符为终结符，则直接将其加入 FIRST 集中
if (prod.Length > 0 && IsTerminal(prod[0]))
{
if (!firsts1[symbol].Contains(prod[0].ToString()))
firsts1[symbol].Add(prod[0].ToString());
continue;
}
// 如果产生式首字符为非终结符，则计算该非终结符的 FIRST 集，并将结果加入首字符的 FIRST 集中
else if (prod.Length > 0 && !IsTerminal(prod[0]))
{
GetFirst(prod[0].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[0].ToString()])
{
if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
firsts1[symbol].Add(f);
}
}
//如果第一个非终结符能推出#
if (IsReachEmpty(prod[0].ToString(), production1))
{
// 递归计算第二个和后面的字符的 FIRST 集，并将结果加入该非终结符的 FIRST 集中
for (int j = 1; j < prod.Length; j++)
{
if (IsTerminal(prod[j]))
{
if (!firsts1[symbol].Contains(prod[j].ToString()))
firsts1[symbol].Add(prod[j].ToString());
break;
}
GetFirst(prod[j].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[j].ToString()])
{
if (!firsts1[symbol].Contains(f) && !f.Equals('#'))
firsts1[symbol].Add(f);
}
// 如果该非终结符的 FIRST 集没有包含空串，则可以结束循环
if (!IsReachEmpty(prod[j].ToString(), production1))
{
break;
}
// 如果是最后一个字符且所有非终结符的 FIRST 集都含有空串，则将空串加入该非终结符的 FIRST 集中
if (j == prod.Length - 1)
{
if (!firsts1[symbol].Contains("#"))
firsts1[symbol].Add("#");
}
}
}
}
}
// 计算 FOLLOW 集
private void GetFollow(string symbol, Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
// 如果该非终结符的 FOLLOW 集已经被计算出，则直接返回
if (follows1.ContainsKey(symbol))
{
return;
}
follows1.Add(symbol, new List<string>());
// 如果是起始符号，则将 # 加入 FOLLOW 集中
if (symbol.Equals(production1.Keys.First()))
{
if (!follows1[symbol].Contains("#"))
follows1[symbol].Add("#");
}
// 遍历产生式，计算 FOLLOW 集
foreach (var item in production1)
{
foreach (var prod in item.Value)
{
int index = prod.IndexOf(symbol);
if (index == -1)
continue;
// 如果该非终结符位于产生式末尾，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (index == prod.Length - 1)
{
GetFollow(item.Key, production1, firsts1, follows1);
foreach (var f in follows1[item.Key])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
else
{
// 如果该非终结符后面是终结符，则将该终结符加入该非终结符的 FOLLOW 集中
if (IsTerminal(prod[index + 1]))
{
if (!follows1[symbol].Contains(prod[index + 1].ToString()))
follows1[symbol].Add(prod[index + 1].ToString());
}
// 如果该非终结符后面是非终结符，则将该非终结符的 FIRST 集加入该非终结符的 FOLLOW 集中
else
{
GetFirst(prod[index + 1].ToString(), production1, firsts1);
foreach (var f in firsts1[prod[index + 1].ToString()])
{
if (!f.Equals("#") && !follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
// 如果该非终结符后面的所有符号都能推出空串，则将产生式左部的 FOLLOW 集加入该非终结符的 FOLLOW 集中
if (IsReachEmpty(prod[index + 1].ToString(), production1))
{
GetFollow(item.Key, production1, firsts1, follows1);
foreach (var f in follows1[item.Key])
{
if (!follows1[symbol].Contains(f))
follows1[symbol].Add(f);
}
}
}
}
}
}
}
private void GetSelect(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1)
{
//对非终结符的每个产生式获取select值
//如果该产生式第一个字符为终结符
//如果该产生式第一个字符为非终结符
// 对每个非终结符进行操作
// 对每个非终结符进行遍历
foreach (var nonterm in nonterminals)
{
// 获取该非终结符的所有产生式
var productions = production1[nonterm];
// 遍历该非终结符的所有产生式
foreach (var prod in productions)
{
// 初始化该产生式的 select 值
List<string> select = new List<string>();
// 如果该产生式的第一个字符为终结符，直接将该字符加入 select
if (IsTerminal(prod[0]))
{
if (prod[0].Equals('#'))
{
// 如果该产生式的第一个字符为 #，将 follow(nonterm) 加入 select
select.AddRange(follows1[nonterm]);
}
else
{
// 如果该产生式的第一个字符为其他终结符，将该终结符加入 select
select.Add(prod[0].ToString());
}
}
else
{
// 如果该产生式的第一个字符为非终结符，将该非终结符的 first 集加入 select
select.AddRange(firsts1[prod[0].ToString()]);
// 如果该非终结符的 first 集中包含空串，将 follow(nonterm) 加入 select
if (select.Contains("#"))
{
select.Remove("#");
select.AddRange(follows1[nonterm]);
}
}
// 将该产生式的 select 值加入预测分析表中
foreach (var term in select)
{
table[nonterm][term] = prod;
}
}
}
}
private void button7_Click(object sender, EventArgs e)
{
string text = textBox1.Text;
analyse_sentence analyse = new analyse_sentence(text, select);
listView4.Items.Clear();
for (int i = 0; i < analyse.result_analys.Count; i++)
{
ListViewItem item = new ListViewItem(new string[] { analyse.result_analys[i], analyse.result_input[i], analyse.result_parse[i] });
listView4.Items.Add(item);
}
}
private void button8_Click(object sender, EventArgs e)
{
string text = textBox1.Text;
analyse_sentence analyse = new analyse_sentence(text, select);
listView4.Items.Clear();
for (int i = 0; i < analyse.result_analys.Count; i++)
{
ListViewItem item = new ListViewItem(new string[] { analyse.result_analys[i], analyse.result_input[i], analyse.result_parse[i] });
listView4.Items.Add(item);
System.Threading.Thread.Sleep(500);
}
}
private void button9_Click(object sender, EventArgs e)
{
string text = textBox1.Text;
analyse_sentence analyse = new analyse_sentence(text, select);
listView4.Items.Clear();
for (int i = 0; i < analyse.result_analys.Count; i++)
{
ListViewItem item = new ListViewItem(new string[] { analyse.result_analys[i], analyse.result_input[i], analyse.result_parse[i] });
listView4.Items.Add(item);
}
}
}
}
代码说明：
-
analyse_sentence类- 用于实现 LL(1) 语法分析，包含了分析栈、输入栈、分析结果等信息。
analyseresult()方法实现语法分析过程，并记录分析过程的步骤。addanalyse()方法用于将推出的产生式加入分析栈。IsTerminal()方法判断字符是否为终结符。
-
Form4类button4_Click()方法用于预处理文法，计算 FIRST 集、FOLLOW 集、SELECT 集。GetFirst()方法用于计算 FIRST 集。GetFollow()方法用于计算 FOLLOW 集。GetSelect()方法用于计算 SELECT 集。button7_Click()方法用于分析 textBox1 中的字符，并将结果显示在 listView4 中。button8_Click()方法用于单步显示分析过程，每 500 毫秒显示一步。button9_Click()方法用于一键显示分析过程。
代码功能：
- 输入 LL(1) 文法规则。
- 计算 FIRST 集、FOLLOW 集、SELECT 集。
- 对输入的字符进行语法分析。
- 显示分析过程，包括分析栈、输入栈、分析结果。
使用方法：
- 在
richTextBox1中输入 LL(1) 文法规则，每条规则用回车符分隔。 - 点击
button4按钮进行预处理。 - 在
textBox1中输入待分析的字符串。 - 点击
button7按钮进行分析，结果将显示在listView4中。 - 点击
button8按钮进行单步显示分析过程。 - 点击
button9按钮进行一键显示分析过程。
注意：
- 文法规则必须是 LL(1) 文法，否则可能无法正常分析。
- 输入的字符串必须符合文法规则，否则将导致分析失败。
示例：
文法规则：
E -> T + E | T
T -> F * T | F
F -> ( E ) | id
待分析的字符串：
( id + id ) * id
分析结果：
分析栈 | 输入栈 | 分析结果
------- | -------- | --------
# | id * id ) + id ( # | #
# E | id * id ) + id ( # | #
# T | id * id ) + id ( # | #
# F | id * id ) + id ( # | #
# ( | id * id ) + id ( # | #
# E | * id ) + id ( # | #
# T | * id ) + id ( # | #
# F | * id ) + id ( # | #
# id | * id ) + id ( # | #
# | * id ) + id ( # | #
# * | id ) + id ( # | #
# * T | id ) + id ( # | #
# * F | id ) + id ( # | #
# * id | ) + id ( # | #
# * | ) + id ( # | #
# ) | ) + id ( # | #
# | + id ( # | #
# + | id ( # | #
# + E | id ( # | #
# + T | id ( # | #
# + F | id ( # | #
# + id | ( # | #
# + | ( # | #
# | # | 成功
代码中还包含了如下方法：
IsReachEmpty(string symbol, Dictionary<string, List<string>> production1): 判断非终结符是否能推出空串。JudgeLL1(Dictionary<string, List<string>> production1, Dictionary<string, List<string>> firsts1, Dictionary<string, List<string>> follows1): 判断文法是否是 LL(1) 文法。
代码示例中的 select 变量需要根据预处理后的文法信息进行初始化。
原文地址: https://www.cveoy.top/t/topic/fXKh 著作权归作者所有。请勿转载和采集!