C 语言递归下降解析器程序

2024年8月28日 | 阅读 4 分钟

引言

解析过程涉及确定给定程序是否合法。它检查输入字符串以查看其是否符合既定语法。

解析器分为两种

1. 自顶向下解析器

这些解析器从树的根部开始，向下遍历到其叶子。递归下降解析器和LL 解析器是自顶向下解析器的两个示例。

2. 自底向上解析器

使用这种解析技术，整个程序被简化为起始符号。自底向上解析器包括运算符优先级解析器、LR(0) 解析器、SLR 解析器、LALR 解析器和CLR 解析器。

什么是递归下降解析器？

像解析器这样的持续下降自顶向下解析器，从根到叶构建解析树。它使用递归函数识别输入，并且可能使用也可能不使用回溯。预测解析是递归下降解析器的一种变体，不需要回溯。

回溯

您可以遵循几个步骤来使用回溯

它会重复扫描输入，直到我们找到正确的路径。
为了创建递归下降解析器，语法必须具备以下品质
不应允许重复。
它需要进行左因子分解。备选项不应共享前缀。
语言应该支持递归。
如果语法未进行左因子分解，递归下降解析器将需要回溯。

示例

在消除左递归之前	在消除左递归之后
E -> E + T \| T T -> T * F \| F F ->( E ) \| id	E -> T E' E' -> + T E' \| e T -> F T' T' -> * F T' \| e F ->( E ) \| id

现在，我们将为递归下降解析器中的每个变量创建一个单独的程序。

程序

#include <stdio.h>
#include <string.h>

#define SUCCESS 1
#define FAILED 0

int E(), Edash(), T(), Tdash(), F();

const char *cursor;
char string[64];

int main()
{
	puts("Enter the string");
	// scanf("%s", string);
	sscanf("i+(i+i)*i", "%s", string);
	cursor = string;
	puts("");
	puts("Input		 Action");
	puts("--------------------------------");

	if (E() && *cursor == '\0') {
		puts("--------------------------------");
		puts("String is successfully parsed");
		return 0;
	} else {
		puts("--------------------------------");
		puts("Error in parsing String");
		return 1;
	}
}

int E()
{
	printf("%-16s E -> T E'\n", cursor);
	if (T()) {
		if (Edash())
			return SUCCESS;
		else
			return FAILED;
	} else
		return FAILED;
}

int Edash()
{
	if (*cursor == '+') {
		printf("%-16s E' -> + T E'\n", cursor);
		cursor++;
		if (T()) {
			if (Edash())
				return SUCCESS;
			else
				return FAILED;
		} else
			return FAILED;
	} else {
		printf("%-16s E' -> $\n", cursor);
		return SUCCESS;
	}
}

int T()
{
	printf("%-16s T -> F T'\n", cursor);
	if (F()) {
		if (Tdash())
			return SUCCESS;
		else
			return FAILED;
	} else
		return FAILED;
}

int Tdash()
{
	if (*cursor == '*') {
		printf("%-16s T' -> * F T'\n", cursor);
		cursor++;
		if (F()) {
			if (Tdash())
				return SUCCESS;
			else
				return FAILED;
		} else
			return FAILED;
	} else {
		printf("%-16s T' -> $\n", cursor);
		return SUCCESS;
	}
}

int F()
{
	if (*cursor == '(') {
		printf("%-16s F -> ( E )\n", cursor);
		cursor++;
		if (E()) {
			if (*cursor == ')') {
				cursor++;
				return SUCCESS;
			} else
				return FAILED;
		} else
			return FAILED;
	} else if (*cursor == 'i') {
		cursor++;
		printf("%-16s F ->i\n", cursor);
		return SUCCESS;
	} else
		return FAILED;
}

输出

Enter the string

Input		 Action
--------------------------------
i+(i+i)*i        E -> T E'
i+(i+i)*i        T -> F T'
+(i+i)*i         F ->i
+(i+i)*i         T' -> $
+(i+i)*i         E' -> + T E'
(i+i)*i          T -> F T'
(i+i)*i          F -> ( E )
i+i)*i           E -> T E'
i+i)*i           T -> F T'
+i)*i            F ->i
+i)*i            T' -> $
+i)*i            E' -> + T E'
i)*i             T -> F T'
)*i              F ->i
)*i              T' -> $
)*i              E' -> $
*i               T' -> * F T'
                 F ->i
                 T' -> $
                 E' -> $
--------------------------------
String is successfully parsed

递归下降解析器：优点和缺点

递归下降解析器有几个优点和缺点。递归下降解析器的一些主要优点和缺点如下：

优点

实现递归下降解析器相当简单。它们非常适合“快速而粗糙”的场景。

缺点

这些解析器比其他一些解析器慢。对于需要任意长超前的解析，它们效率低下。
只有支持递归过程调用的语言才能实现。它存在左递归问题。

下一主题C 语言中 exit() 和 return() 的区别

← prev next →

C 语言递归下降解析器程序

引言

什么是递归下降解析器？

回溯

示例

程序

递归下降解析器：优点和缺点

优点

缺点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言递归下降解析器程序

引言

什么是递归下降解析器？

回溯

示例

程序

递归下降解析器：优点和缺点

优点

缺点

相关帖子

C 语言 realloc

C 语言轮询程序及输出

C 语言函数原型

C 语言 Execlp() 函数

C 语言旅行商问题

C 语言数字图案程序

C 语言平方根

C 语言 isgraph() 函数

C/C++ 中清空输入缓冲区

C 语言插入排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器