【编译Chap4】求first集、follow集例题-北京尧图网络

【编译Chap4】求first集、follow集例题

方法求 FIRST 集的规则反复扫描所有产生式以A → X 1 X 2 ⋯ X n A\to X_1X_2\cdots X_nA→X1X2⋯Xn为例依次处理X i X_iXii从1 to n把F I R S T ( X i ) − { ε } \mathrm{FIRST}(X_i)-\{\varepsilon\}FIRST(Xi)−{ε}加入F I R S T ( A ) \mathrm{FIRST}(A)FIRST(A)如果ε ∉ F I R S T ( X i ) \varepsilon\notin \mathrm{FIRST}(X_i)ε∈/FIRST(Xi)停止处理该产生式如果ε ∈ F I R S T ( X i ) \varepsilon\in\mathrm{FIRST}(X_i)ε∈FIRST(Xi)继续处理下一个X i 1 X_{i1}Xi1如果所有X i X_iXi都能推出ε \varepsilonε则把ε \varepsilonε加入F I R S T ( A ) \mathrm{FIRST}(A)FIRST(A)。求 FOLLOW 集的规则开始符号把$输入结束符放入开始符号的 FOLLOW 集。反复扫描所有产生式以A → α B β A \to \alpha B \betaA→αBβ为例把F I R S T ( β ) − { ε } \mathrm{FIRST}(\beta) - \{\varepsilon\}FIRST(β)−{ε}加入F O L L O W ( B ) \mathrm{FOLLOW}(B)FOLLOW(B)。可空情况如果β \betaβ能推导出ε \varepsilonε即ε ∈ F I R S T ( β ) \varepsilon \in \mathrm{FIRST}(\beta)ε∈FIRST(β)或者B BB在产生式最右边则把F O L L O W ( A ) \mathrm{FOLLOW}(A)FOLLOW(A)加入F O L L O W ( B ) \mathrm{FOLLOW}(B)FOLLOW(B)。Appendix如果有左递归先消除左递归消除直接左递归的方法最简单的情况A → A α ∣ β A \to A\alpha \mid \betaA→Aα∣β改写为A → β A ′ A ′ → α A ′ ∣ ε \begin{aligned} A \to \beta A \\ A \to \alpha A \mid \varepsilon \end{aligned}AA′→βA′→αA′∣ε一般形式A → A α 1 ∣ A α 2 ∣ ⋯ ∣ A α m ∣ β 1 ∣ β 2 ∣ ⋯ ∣ β n A \to A\alpha_1 \mid A\alpha_2 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_nA→Aα1∣Aα2∣⋯∣Aαm∣β1∣β2∣⋯∣βn改写为A → β 1 A ′ ∣ β 2 A ′ ∣ ⋯ ∣ β n A ′ A ′ → α 1 A ′ ∣ α 2 A ′ ∣ ⋯ ∣ α m A ′ ∣ ε \begin{aligned} A \to \beta_1 A \mid \beta_2 A \mid \cdots \mid \beta_n A \\ A \to \alpha_1 A \mid \alpha_2 A \mid \cdots \mid \alpha_m A \mid \varepsilon \end{aligned}AA′→β1A′∣β2A′∣⋯∣βnA′→α1A′∣α2A′∣⋯∣αmA′∣εAppendixLL1表的构造遍历所有产生式以A → α为例对每个终结符 a ∈ FIRST(α)把 A → α 加至 M[A, a]中其中 α 为含有首字符 a 的候选式或唯一的候选式若ε ∈ FIRST(A)则对任何 b ∈ FOLLOW(A) 把 A → ε 加至 M[A, b]中六道例题第一题答案第二题答案firstAabcdgBbεCacdDdεEcgfollow不要忘记$求first非常容易错知乎有很好的方法论若X-a…则将终结符加入FIRST(X)中;注意非终结符的情况若X-e ,则将终结符e加入FIRST(X)中(e表示空集)若 X-BC…D,则将FirstB所有元素除了空集加入FirstX然后检测FirstB若FirstB中不存在空集, 即e,则停止若存在则向B的后面查看将FirstC中所有元素除了空集加入FirstX然后再检测FirstC中是否有e…直到最后若D之前的所有非终结符的First集中都含有e,则检测到D时将FirstD也加入FirstX若FirstD中含有e,则将 e加入FirstX。总之看到epsilon要继续往后找直到没有epsilon或能确定X可置空为止。再一个简单例子下面的不能因为A的first集是epsilonS的第一个符号是A所以S的first集中就是epsilon这是不对的first集中有epsilon代表该符号可置空而在下面这个例题中S推不出空。所以此时应该向后找A的后面是aa的first是本身a到这里就可以停止了。第三题first:S: a,b,εAa,bBa,bfollow:第四题2010期末A卷第二题第五题lws 模拟试卷一第二题第六题ref:https://blog.csdn.net/Baron_wu/article/details/84994254https://blog.csdn.net/RENSRM/article/details/111595754https://zhuanlan.zhihu.com/p/268555826

RELATED

相关推荐

Hadoop电信客服分析链路：从混杂日志到交互式业务看板

Hadoop电信客服分析链路：从混杂日志到交互式业务看板

简介：本资源是一个面向大数据初学者与电信行业数据工程师的Hadoop全栈实战项目，聚焦客服数据采集、存储、分析与可视化闭环。项目基于真实业务场景，整合Zookeeper集群协调、HBase实时存储、Flume日志采集、Kafka流式分发及HDFSMapReduce批处理…

📅 2026/10/19 1:15:01

循环架构大揭秘：Dory1.0-4B 的 normalized-GPT 与混合注意力如何炼成 256K 长上下文

循环架构大揭秘：Dory1.0-4B 的 normalized-GPT 与混合注意力如何炼成 256K 长上下文

人工智能大模型推理模型模型量化【免费下载链接】NVIDIA-Nemotron-Labs-Dory1.0-4B-MXFP8 项目地址： https://ai.gitcode.com/hf_mirrors/nvidia/NVIDIA-Nemotron-Labs-Dory1.0-4B-MXFP8 点击查看免费下载 NVIDIA-Nemotron-Labs-Dory1.0-4B-MXFP8 是 NVIDIA 推出…

📅 2026/10/19 1:15:01

基于溯源图与图神经网络的APT攻击链检测方法

基于溯源图与图神经网络的APT攻击链检测方法

简介：一份基于溯源图的APT攻击检测方法优化Python实现源码，适合信息安全、计算机科学、数据科学等专业学生用于毕业设计、课程设计或期末大作业。项目代码已经过功能验证，可稳定运行，并提供清晰的目录结构与注释，便于二…

📅 2026/10/19 1:15:01

MORE NEWS

更多资讯

Escrcpy 安卓镜像完整教程：10 分钟投屏上手，鼠标键盘接管手机

Escrcpy 安卓镜像完整教程：10 分钟投屏上手，鼠标键盘接管手机【免费下载链接】escrcpy 📱 Display and control your Android device graphically with scrcpy. 项目地址: https://gitcode.com/GitHub_Trending/es/escrcpy Escrcpy 是…

如何快速上手ConsiSpace：新手友好的模型下载、加载与首次推理完整教程

人工智能大模型多模态计算机视觉【免费下载链接】ConsiSpace 项目地址： https://ai.gitcode.com/BAAI/ConsiSpace 点击查看免费下载 ConsiSpace 是由北京大学计算机学院唐浩团队与北京智源人工智能研究院（BAAI）联合研究推出的空间推理多模…

STM32寄存器手册第三章精讲：时钟系统与GPIO底层配置实战

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026 最实用 Codex 教程（程序员实操版）：从 npm 安装到 Go/Gin 项目接入 TaoToken

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

UGNX开发--解析NX图纸对象系列（一）：用TaoToken统一管理NXOpen与UFUN的图纸对象调试环境

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

【WebSocket】 WebSocket 是否支持压缩？如何启用 permessage-deflate 扩展？

WebSocket 压缩深度解析：permessage-deflate 扩展的原理与实战应用用户问题原文：WebSocket 是否支持压缩？如何启用 permessage-deflate 扩展？在构建直播互动弹幕系统时，我们曾因未启用 WebSocket 压缩导致带宽成本飙升 300%，单场热门直播的 CDN 费用高达数万元。根本原…

TODAY

今日更新

悟空开源无代码平台实战：从实体建模到应用设计避坑指南

简介：基于悟空开源无代码平台的多种应用设计源码，面向希望在不编写代码的情况下快速搭建CRM、HRM、财务系统、ERP、SRM等业务应用的企业与技术人员，通过拖放式界面和内置模板即可完成应用定制与部署。压缩包共697个文件，约10.74MB…

基于.NET9的多租户权限系统：数据权限与动态API落地实践

简介：这份资源是一套面向 .NET 与 Vue 全栈开发者的中台权限管理系统，后端基于 .Net9，前端采用 Vue3 Element Plus，并配套 uniapp uviewui 移动端方案，实现前后端分离。系统覆盖多租户隔离、数据权限、动态 Api、任务…

场地预约小程序毕设实战：SSM+微信小程序+MySQL数据库设计到避坑

简介：面向毕业设计场景的场地预约小程序完整项目，基于微信小程序SSMMySql技术栈开发，适合计算机相关专业学生作为选题参考、功能扩展或二次开发起点。系统实现场地类型管理、场地管理、预约管理、取消申请与押金退回等功能，分为管…

THIS WEEK

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

简介：这份PDF报告聚焦2025年金融服务业中国AI现状与趋势，面向金融科技从业者、AI战略规划人员及关注行业数字化转型的研究者，帮助读者把握生成式AI在银行、支付、交易等场景中的落地路径与投资方向。资源包内含1个PDF文件，大小约1…

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

基于GMM的语音识别系统原理与MATLAB实现详解

说到基于高斯混合模型（GMM）的语音识别系统，很多人第一反应就是一堆数学公式，觉得门槛很高。但如果你真的在MATLAB里把它落地跑通，会发现核心其实就是三件事：把声音变成特征向量，用GMM给每个类别…

THIS MONTH

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

读完文章，想聊聊您的网站？

告诉我们您的行业与需求，资深顾问一对一梳理方案与报价，全程免费。

免费获取方案 400-888-6620

📞 💬