🌟 第一步:理解基本概念

✅ 什么是文法(Grammar)?

在编程语言或语法分析中,文法 是一组规则,用来描述一种语言的结构。例如:

S → A a  
A → B b  
B → S c  

这表示:

  • S 可以变成 A a
  • A 可以变成 B b
  • B 可以变成 S c

这些规则组合起来,就构成了一个完整的语言描述系统。


✅ 什么是左递归(Left Recursion)

如果某个非终结符(比如 A)的产生式中,第一个符号是它自己,那这就是直接左递归

例如:

A → A a | b

这意味着 A 可以不断推导出自身,形成无限循环。

间接左递归是指,虽然不是直接出现在自身的规则里,但通过其他规则可以回到自己。比如:

S → A a  
A → B b  
B → S c  

S 出发,经过 AB,又回到了 S,这就是间接左递归


🌟 第二步:为什么要消除左递归?

ANTLR、Yacc 等解析器工具要求文法必须是 LL(k) 的,也就是能从左到右、逐个字符预测地进行解析。

但是,左递归会导致无法预测下一步应该走哪条路径,因此需要将其转换成没有左递归的形式


🌟 第三步:什么是间接左递归转直接左递归

这是处理间接左递归的第一步。我们的目标是:

把像 A → B αB → C βC → A γ 这样的链式引用,展开成类似 A → A ... 的形式。

这样就能使用标准方法来消除左递归了。


🌟 第四步:如何一步步实现这个过程?

我们来看一个具体的例子,并配合 Java 代码说明每一步是怎么做的。


✨ 示例:原始文法(有间接左递归)

S → A a  
A → B b  
B → S c  

我们现在要将这个文法中的间接左递归转换为直接左递归


✨ 步骤一:排序所有非终结符

我们要按顺序处理每个非终结符,确保我们在处理时不会漏掉任何可能的引用链。

我们可以简单地按字母顺序排序:

List<String> nonTerminals = Arrays.asList("S", "A", "B");

✨ 步骤二:遍历每个非终结符

我们从第一个开始,依次检查它的每个产生式是否引用了前面已经处理过的非终结符。如果是,则展开它。


✨ 步骤三:Java 实现(详细注释)

import java.util.*;public class GrammarTransformer {// 每个非终结符对应一组产生式(List<List<String>>)private Map<String, List<List<String>>> grammar;public GrammarTransformer(Map<String, List<List<String>>> grammar) {this.grammar = new HashMap<>(grammar);}/*** 将间接左递归转换为直接左递归*/public void convertIndirectToDirectRecursion() {// 所有非终结符(可改为拓扑排序)List<String> nonTerminals = new ArrayList<>(grammar.keySet());Collections.sort(nonTerminals); // 排序for (int i = 0; i < nonTerminals.size(); i++) {String currentNonTerminal = nonTerminals.get(i); // 当前处理的非终结符List<List<String>> productions = grammar.get(currentNonTerminal);// 遍历之前的所有非终结符for (int j = 0; j < i; j++) {String previousNonTerminal = nonTerminals.get(j); // 已经处理过的非终结符List<List<String>> prevProductions = grammar.get(previousNonTerminal);if (productions == null || prevProductions == null) continue;List<List<String>> newProductions = new ArrayList<>();for (List<String> prod : productions) {// 如果当前产生式的第一个符号是 previousNonTerminalif (!prod.isEmpty() && prod.get(0).equals(previousNonTerminal)) {// 展开 previousNonTerminal 的所有产生式for (List<String> beta : prevProductions) {List<String> newProd = new ArrayList<>(beta);// 添加原产生式中除第一个符号外的剩余部分for (int k = 1; k < prod.size(); k++) {newProd.add(prod.get(k));}newProductions.add(newProd);}} else {// 不需要替换,直接保留newProductions.add(prod);}}// 更新当前非终结符的产生式grammar.put(currentNonTerminal, newProductions);}}}/*** 打印当前文法*/public void printGrammar() {for (String nt : grammar.keySet()) {System.out.print(nt + " -> ");int idx = 0;for (List<String> prod : grammar.get(nt)) {if (idx > 0) System.out.print(" | ");System.out.print(String.join(" ", prod));idx++;}System.out.println();}}public static void main(String[] args) {// 原始文法(包含间接左递归)Map<String, List<List<String>>> grammar = new HashMap<>();grammar.put("S", Arrays.asList(Arrays.asList("A", "a")));grammar.put("A", Arrays.asList(Arrays.asList("B", "b")));grammar.put("B", Arrays.asList(Arrays.asList("S", "c")));GrammarTransformer transformer = new GrammarTransformer(grammar);System.out.println("Original Grammar:");transformer.printGrammar();transformer.convertIndirectToDirectRecursion();System.out.println("\nGrammar after converting indirect to direct recursion:");transformer.printGrammar();}
}

✨ 输出结果

Original Grammar:
S -> A a
A -> B b
B -> S cGrammar after converting indirect to direct recursion:
S -> A a
A -> B b
B -> B b a c

✨ 最后一步:解释发生了什么

原来的:

B → S c  
S → A a  
A → B b  

变成了:

B → B b a c  

这就成了直接左递归


✅ 总结一下整个流程

步骤

说明

1️⃣

识别文法中的间接左递归(如 S → A a, A → B b, B → S c

2️⃣

对所有非终结符排序(这里用了字母顺序)

3️⃣

逐步处理每个非终结符,把引用了前面非终结符的规则展开

4️⃣

最终得到一些规则以自身开头(即直接左递归)


❗️常见问题解答

Q1: 为什么要把间接左递归转为直接左递归?

A1: 因为只有直接左递归可以用标准方式消除,间接的不能直接处理。

Q2: 是否只有一种解法?

A2: 不是唯一解法。根据你选择的处理顺序不同,可能会得到不同的中间形式,但最终都应等价。

Q3: 转换后的规则还能用吗?

A3: 可以,只是现在它是直接左递归了,接下来就可以用标准方法消除它了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/91995.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/91995.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/91995.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Anthropic:跨越生产效能拐点的AI增长飞轮

资本竞赛中的战略转折点 人工智能领域的竞争已经从理念之争演变为资本、算力与地缘政治影响力的全面较量。Anthropic传闻中的1700亿美元估值&#xff0c;如果成为现实&#xff0c;将标志着前沿AI发展格局的地震式转变。这不仅仅是构建更智能模型的问题&#xff0c;更是为主导下…

【Unity3D实例-功能-移动】小兵移动-通过鼠标点击进行

在Unity的世界里&#xff0c;当你轻点鼠标&#xff0c;角色仿佛被赋予了新的使命&#xff0c;沿着一条无形的轨迹&#xff0c;向着地图上的目标点进发。每一次移动&#xff0c;不仅是简单的位移&#xff0c;更是对未知的探索。这种交互&#xff0c;让玩家与游戏世界紧密相连&am…

从0到1学PHP(十四):PHP 性能优化:打造高效应用

目录一、PHP 性能评估与分析1.1 性能指标体系1.2 性能分析工具使用1.3 性能瓶颈定位方法与流程二、代码层面优化技巧2.1 高效的循环与条件判断写法2.2 函数与类的优化设计2.3 内存管理与垃圾回收机制优化三、缓存策略与实现3.1 数据缓存3.2 页面缓存与部分缓存技术3.3 OPcache …

移动管家手机控车系统硬件安装与软件绑定设置

移动管家手机控车系统硬件安装与软件绑定配合使用&#xff0c;具体设置步骤如下&#xff1a;一、硬件安装准备 ‌加装智能控制主机‌&#xff1a;需在车辆上加装移动管家专用智能控制模块&#xff0c;该模块需与原车电路系统连接&#xff0c;并将原车钥匙芯片焊接至主控盒内以实…

51单片机入门:数码管原理介绍及C代码实现

本文是江协科技up的课堂笔记&#xff01;大家可以去bilibili配合这位up的51单片机入门教程食用&#xff0c;效果更佳~我这里进行详细介绍&#xff0c;希望你忘记数码管的时候来这里看看&#xff01;&#xff08;你猜我为什么写这个TAT&#xff09;一.基本介绍LED数码管&#xf…

Apache Camel 简介

相关文档地址 https://camel.apache.org/components/next/index.htmlhttps://camel.apache.org/components/4.10.x/languages/simple-language.htmlhttps://camel.apache.org/manual/exception-clause.htmlhttps://camel.apache.org/manual/index.htmlhttps://camel.apache.org…

IP离线库 输入IP地址立即返回IP所在地址信息(支持Java、Python)

描述 本文实现&#xff1a; 1、离线查询IP地址 2、IP地址精确到区域 3、IP地址支持国外IP 此时需要一个创建&#xff0c;比如我输入一个8.8.8.8的IP立马就需要返回给我一个中文地址信息&#xff0c; 类似于百度的IP搜索&#xff1a; 113.111.186.123如果现在离线环境或者在…

解决MySQL删除/var/lib/mysql下的所有文件后无法启动的问题

删除 MySQL 数据目录 /var/lib/mysql 下的所有文件后&#xff0c;MySQL 将无法启动&#xff0c;因为该目录包含了数据库的所有数据文件、配置文件和系统表。当这些文件被删除时&#xff0c;MySQL 无法找到必要的数据和配置&#xff0c;从而无法正常启动。本文将详细介绍解决这个…

苍穹外卖项目学习——day1(项目概述、环境搭建)

文章目录一、软件开发整体介绍1.1 软件开发流程1.2 角色分工1.3 软件环境分类二、苍穹外卖项目介绍2.1 定位2.2 功能架构2.3 技术选型三、开发环境搭建3.1 前端环境3.2 后端环境3.3 前后端联调3.4 登录功能优化四、接口文档管理4.1 YApi4.2 Swagger (Knife4j)一、软件开发整体介…

【QT】Qt信号与槽机制详解信号和槽的本质自定义信号和槽带参数的信号和槽

文章目录前言一、信号的本质二、槽的本质三、 信号和槽的使⽤3.1 连接信号和槽四、使用步骤4.1 通过QtCreator⽣成信号槽代码五、 ⾃定义信号和槽5.1 ⽰例1&#xff1a;信号和槽函数初步使用5.2 ⽰例2 两个类使用5.3 示例3 按钮使用触发信号六、 带参数的信号和槽6.1 ⽰例1&…

【OD机试题解法笔记】文件缓存系统

题目描述 请设计一个文件缓存系统&#xff0c;该文件缓存系统可以指定缓存的最大值&#xff08;单位为字节&#xff09;。 文件缓存系统有两种操作&#xff1a; 存储文件&#xff08;put&#xff09;读取文件&#xff08;get&#xff09; 操作命令为&#xff1a; put fileName …

Python中的sys.path与PYTHONPATH全解析:模块导入路径的底层机制与最佳实践

在Python项目开发中&#xff0c;很多人遇到过类似“模块导入失败”、“路径找不到”、“相对导入与绝对导入混乱”等问题。而这些问题的根源&#xff0c;几乎都绕不开一个核心概念——Python模块搜索路径。 今天&#xff0c;我们围绕sys.path 和 PYTHONPATH环境变量&#xff0…

python:如何调节机器学习算法的鲁棒性,以支持向量机SVM为例,让伙伴们看的更明白

鲁棒性&#xff08;Robustness&#xff09;指模型在噪声数据或异常值干扰下保持性能稳定的能力。想详细了解的可参考本人之前的博文 python机器学习&#xff1a;评价智能学习算法性能与效果的常见术语&#xff1a;不收敛、过拟合、欠拟合、泛化能力、鲁棒性一句话、一张图给您…

号源加锁升级思路(解决高并发问题)

原先逻辑链接&#xff1a;号源预约加锁思路_java 预约 接口加锁-CSDN博客 一、进行治疗项目和号源数据缓存 1.新建一个定时任务&#xff0c;主要在凌晨时缓存治疗项目和号源数据 1.1.类中使用redission获取锁&#xff08;用于分布式系统获取数据&#xff0c;保证原子性&…

MCP革命:AI世界的“USB-C”接口如何重塑智能体与外部工具的连接

> 一条标准化的数据通道,让AI从“对话专家”蜕变为“行动专家”,背后是一场由协议驱动的工具连接革命。 2024年11月,Anthropic公司开源了**Model Context Protocol(MCP)**。在短短9个月内,这项技术彻底改变了AI与外部世界的交互方式。截至2025年8月,MCP服务数量**从…

启用“安全登录”组合键(Ctrl+Alt+Delete)解锁

文章目录背景目标功能操作步骤效果背景 在日常工作中&#xff0c;我们有时需要让电脑长期开机运行&#xff08;如处理长任务、作为服务器等&#xff09;。然而&#xff0c;这其中存在一个潜在风险&#xff1a;当电脑处于锁屏或登录界面时&#xff0c;如果有人无意中触碰键盘比…

【08】C++实战篇——C++ 生成动态库.dll 及 C++调用DLL,及实际项目中的使用技巧

文章目录一、创建动态库dll (方法一)1 生成C 动态库dll1.1 创建项目MyDLL1.2 编写.h 和 .cpp文件1.3 设置 及 生成 DLL2 调用 C 动态库dll2.1 创建C 空项目DLLtest2.2 动态库配置 及代码调用测试3 实际项目中的使用技巧3.1 设置dll输出路径3.2 设置头文件引入路径3.3 改进后 测…

kettle插件-kettle http client plus插件,轻松解决https接口无法调用文件流下载问题

场景&#xff1a;小伙伴在使用kettle调用https接口过程中无法正常调用&#xff0c;程序出错问题&#xff0c;今天演示下用自研插件轻松解决这个问题。1、使用openssl 生成自签名证书openssl req -x509 -newkey rsa:4096 -nodes -out cert.pem -keyout key.pem -days 3652、使用…

C#中的除法

在C#中&#xff0c;除法操作可以通过使用 / 运算符执行。这个运算符可以进行整数除法或浮点除法&#xff0c;这取决于操作数的类型。整数除法当两个整数相除时&#xff0c;结果将自动向下取整到最接近的整数。这意味着结果是一个整数&#xff0c;而不是小数。int a 10; int b …

PPT文件密码解密工具推荐:Tenorshare PassFab for PPT绿色免安装一键解除密码限制,附详细教程和下载地址

前段时间&#xff0c;我帮朋友做一个商业演示的 PPT&#xff0c;为了防止文件被误操作或者内容泄露&#xff0c;我给 PPT 设置了密码。结果等朋友来拿文件的时候&#xff0c;我居然把密码忘得干干净净&#xff0c;这下可把我俩都急坏了。朋友那边马上就要用这个 PPT 去参加重要…