C# 语法分析器(六)构造语法分析器

C# 语法分析器(六)构造语法分析器系列导航(一)语法分析介绍(二)LR(0)语法分析(三)LALR语法分析(四)二义性文法(五)错误恢复(六)构造语法分析器现在支持在运行时通过语法规则生成可以运行的语法分析器,也能够在设计时通过T4模板生成语法分析器,只需要依赖一个较小的运行时Cyjb.Compilers.R

大家好,欢迎来到IT知识分享网。

系列导航

  1. (一)语法分析介绍
  2. (二)LR(0) 语法分析
  3. (三)LALR 语法分析
  4. (四)二义性文法
  5. (五)错误恢复
  6. (六)构造语法分析器

现在支持在运行时通过语法规则生成可以运行的语法分析器,也能够在设计时通过 T4 模板生成语法分析器,只需要依赖一个较小的运行时 Cyjb.Compilers.Runtime。

一、运行时语法规则的定义

语法分析器用到的所有规则都在 Parser

类中定义,这里的泛型参数
T 表示语法分析器的标识符的类型(一般是一个枚举类型),
TController 表示语法分析器的控制器,可以使用默认实现
ParserController<T>。定义规则方法包括:定义产生式的 DefineProduction 方法、定义优先级和结合性的 DefineAssociativity 方法以及定义入口的 AddStart 方法。

调用 DefineProduction 方法定义文法产生式,可以直接指定产生式的头和产生式体,产生式体支持简单的范式(“*”、“+”和“?”)。还可以设置产生式的优先级。

parser.DefineProduction(Calc.E, Calc.Id).Action(c => c[0].Value);

调用 DefineAssociativity 方法定义符号的优先级和结合性,这里的概念与 Bison 一致,也是分为左结合、右结合以及非结合的。

parser.DefineAssociativity(AssociativeType.Left, Calc.Add, Calc.Sub);

调用 AddStart 方法可以定义多个起始非终结符。默认会使用首个出现的非终结符作为起始符号,可以自行添加来覆盖默认符号。这里还支持指定多个起始符号,就可以在一个语法分析器中根据需要分析文法的不同组成部分。

同时,通过设置 ParseOption 参数,还允许扫描到匹配的语法单元后就暂停,而非固定的解析到输入结束,使用上更加灵活。

与词法分析器类似,定义好的语法分析器也可以通过 GetFactory 方法直接生成词法分析器的工厂类,或者也可以使用下面定义设计时语法分析器。

二、设计时语法规则的定义

为了简化设计时语法规则的定义和实现,选择使用 C# Attribute 来指定相关规则,而非语法规则文件。为了使用 T4 模板,需引入一些必备依赖:

  1. 通过 nuget 依赖运行时 Cyjb.Compilers.Runtime。

  2. 通过 nuget 依赖生成器 Cyjb.Compilers.Design,注意请如下指定引用配置,可以正常编译项目并避免产生运行时引用。

<ItemGroup>
	<PackageReference Include="Cyjb.Compilers.Design" Version="1.0.6">
		<GeneratePathProperty>True</GeneratePathProperty>
		<PrivateAssets>all</PrivateAssets>
		<IncludeAssets>compile; build; native; contentfiles; analyzers; buildtransitive</IncludeAssets>
	</PackageReference>
</ItemGroup>

之后就是定义语法规则了。首先要求提供一个继承自 ParserController

的部分类,通过在这个类上定义 Attribute 完成语法规则的定义。

public partial class CalcParser : ParserController<Calc> {
}

使用 ParserProductionAttribute 声明文法的产生式。例如:

public partial class CalcParser : ParserController<Calc> {
	[ParserProduction(Calc.E, Calc.Id)]
	private object? IdAction()
	{
		return this[0].Value;
	}
}

使用 ParserLeftAssociateAttribute、ParserRightAssociateAttribute 和 ParserNonAssociateAttribute 声明优先级和结合性。例如:

// 声明优先级和结合性
[ParserLeftAssociate(Calc.Add, Calc.Sub)]
public partial class CalcParser : ParserController<Calc> {
}

使用 ParserStartAttribute 声明起始符号。例如:

// 声明终结符
[ParserStart(Calc.E)]
public partial class CalcParser : ParserController<Calc> {
}

最后是添加与语法分析器同名的 tt 文件,内容如下:

<#@ include file="$(PkgCyjb_Compilers_Design)\content\CompilerTemplate.t4" #>

运行 T4 模板后即可生成同名的 .designed.cs 文件,包含了语法分析器的实现。下图是一个简单的示例:

图 1 设计时语法分析器示例

图 1 设计时语法分析器示例

语法分析器的核心就是一个 LR 语法分析器,具体实现请参见 LRParser。

三、语法分析的例子

以之前提到的算式文法为例,现在给出完整的实现:

enum Calc { Id, Add, Sub, Mul, Div, Pow, LBrace, RBrace }

Parser<Calc> parser = new();
// 定义产生式
parser.DefineProduction(Calc.E, Calc.Id).Action(c => c[0].Value);
parser.DefineProduction(Calc.E, Calc.E, Calc.Add, Calc.E)
	.Action(c => (double)c[0].Value! + (double)c[2].Value!);
parser.DefineProduction(Calc.E, Calc.E, Calc.Sub, Calc.E)
	.Action(c => (double)c[0].Value! - (double)c[2].Value!);
parser.DefineProduction(Calc.E, Calc.E, Calc.Mul, Calc.E)
	.Action(c => (double)c[0].Value! * (double)c[2].Value!);
parser.DefineProduction(Calc.E, Calc.E, Calc.Div, Calc.E)
	.Action(c =>
	{
		return (double)c[0].Value! / (double)c[2].Value!;
	});
parser.DefineProduction(Calc.E, Calc.E, Calc.Pow, Calc.E)
	.Action(c => Math.Pow((double)c[0].Value!, (double)c[2].Value!));
parser.DefineProduction(Calc.E, Calc.LBrace, Calc.E, Calc.RBrace)
	.Action(c => c[1].Value);
// 定义运算符优先级。
parser.DefineAssociativity(AssociativeType.Left, Calc.Add, Calc.Sub);
parser.DefineAssociativity(AssociativeType.Left, Calc.Mul, Calc.Div);
parser.DefineAssociativity(AssociativeType.Right, Calc.Pow);
parser.DefineAssociativity(AssociativeType.NonAssociate, Calc.Id);

IParserFactory<Calc> factory = Parser.GetFactory();
string text = "1 + 20 * 3 / 4 * (5 + 6)";
Tokenlizer<Calc> tokenlizer = /* 之前词法分析中构造的词法分析器 */
ITokenParser<Calc> parser = factory.CreateParser(tokenizer);
Console.WriteLine(parser.Parse().Value);
// 输出为: 166

相应的设计时语法分析器定义为:

/// <summary>
/// 用于单元测试的计算器控制器。
/// </summary>
[ParserLeftAssociate(Calc.Add, Calc.Sub)]
[ParserLeftAssociate(Calc.Mul, Calc.Div)]
[ParserRightAssociate(Calc.Pow)]
[ParserNonAssociate(Calc.Id)]
public partial class TestCalcParser : ParserController<Calc>
{
	[ParserProduction(Calc.E, Calc.Id)]
	private object? IdAction()
	{
		return this[0].Value;
	}

	[ParserProduction(Calc.E, Calc.E, Calc.Add, Calc.E)]
	[ParserProduction(Calc.E, Calc.E, Calc.Sub, Calc.E)]
	[ParserProduction(Calc.E, Calc.E, Calc.Mul, Calc.E)]
	[ParserProduction(Calc.E, Calc.E, Calc.Div, Calc.E)]
	[ParserProduction(Calc.E, Calc.E, Calc.Pow, Calc.E)]
	private object? BinaryAction()
	{
		double left = (double)this[0].Value!;
		double right = (double)this[2].Value!;
		return this[1].Kind switch
		{
			Calc.Add => left + right,
			Calc.Sub => left - right,
			Calc.Mul => left * right,
			Calc.Div => left / right,
			Calc.Pow => Math.Pow(left, right),
			_ => throw CommonExceptions.Unreachable(),
		};
	}

	[ParserProduction(Calc.E, Calc.LBrace, Calc.E, Calc.RBrace)]
	private object? BraceAction()
	{
		return this[1].Value;
	}
}

现在,完整的语法分析器已经成功构造出来,相关代码都可以在这里找到。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30515.html

(0)
上一篇 2023-11-15 18:45
下一篇 2023-11-18 18:15

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信