写点什么

Treetop——基于 Ruby 的 PEG 解析器生成器

  • 2008-01-22
  • 本文字数:1041 字

    阅读完需:约 3 分钟

Ruby 已经有了一个叫做 RACC 的解析器生成器,是一个 YACC 的移植版本(被用来编写ruby_parser,第一个用Ruby 写成的Ruby 解析器)。

当谈到解析器生成器的时候,解析表达式语法(PEG)最近因为一篇 Bryan Ford 介绍的一种叫做“Packrat 解析”优化的论文而 变得很流行。Packrat 解析解决了诸如指数级解析时间的问题。这是由于解析器使用回溯来解析代码,例如,它们会尝试诸多结果的组合直到找到正确的那一 个。Packrat 解析的解决方法是使用记忆化,例如将解析的中间结果保存下来,而不是一遍一遍的重新计算。这决定了 Packrat 解析的时间复杂度是线 性的,但是缺点是需要很大的内存,通常是源代码大小的几倍。注意,其他的解析器生成器也是采用类似的方法,比如 ANTLR

基于这个前提, Treetop 网站上如此解释 PEG 的优点:

解析表达式语法(PEGs)编写简单、易于维护。它们是简单但功能强大的泛化正则表达式,比起传统的 LALR 或者 LR-1 语法的解析器生成器来说更易于使用。没有必要再进行符号化解析,或者用于有限度上下文敏感的前向断言。

Treetop 会自动生成解析树,而且还允许用户添加方法来定制所生成的节点:
grammar Arithmetic<br></br> rule additive<br></br>  multitive '+' additive {<br></br>  def value<br></br>  multitive.value + additive.value<br></br>  end<br></br>  }<br></br> /<br></br>  multitive<br></br> end<br></br># other rules below ... <br></br>end 这段代码的意思是通过 additive 节点生成的节点有一个叫做 value 的方法。另外,可以为每条规则指定一个要生成的节点类。(注意:这个斜杠是选择操作符,意思是,additive 规则要么是两个操作数和之间的加号,要么是 multitive 规则的结果)。 在开始使用 Treetop 之前,你需要先安装它。可以从Rubyforge 下载Treetop 的源代码,或者通过gem 安装,命令为:

gem install treetop 想要开始使用它的话,可以去查看Treetop 的文档或者看看上文中的示例。Treetop 需要一个简单的算术表达式解析器、一个非常基本的语言解析器以及运行时间。

Treetop 可以通过 tt 工具将语法定义文件转换成 Ruby 代码: <span>tt foo.treetop</span> 另一种选择是通过 Ruby 代码来进行解析器生成
Treetop.load "arithmetic"<br></br>parser = ArithmeticParser.new<br></br><span color="#000000">parser.parse('1+1') </span> Treeop 创始人的现场演示,参见 Nathan Sobo 在 RubyConf 2007 上关于 Treetop 的报告
查看英文原文: Treetop - PEG parser generator for Ruby

2008-01-22 01:171674
用户头像

发布了 80 篇内容, 共 19.8 次阅读, 收获喜欢 5 次。

关注

评论

发布
暂无评论
发现更多内容

Apache Doris 2.0.5 版本正式发布

SelectDB

数据库 大数据 数据仓库 数据分析

周五直播!中国大学生计算机设计大赛数据解读乡村发展赛事培训第一场

ModelWhale

人工智能 大数据 竞赛 高等教育 中国大学生计算机设计大赛

端智能:面向手机计算环境的端云协同AI技术创新

京东零售技术

人工智能 算法 端智能

开启软件架构设计之门:初识软件架构设计的奥秘

灸哥漫谈

架构师 软件架构设计 系统架构师 系统架构设计

我翻遍整个牛客网,整理出了2024最全的Java面试八股文大合集

采菊东篱下

程序员 java面试

Adjustable Precision Shunt Regulator

芯动大师

MySql中BufferPool的基本概念介绍

百度搜索:蓝易云

MySQL Linux 运维 innodb 云服务器

Java面向对象之接口和抽象类的区别一目了然

快乐非自愿限量之名

Java 接口 面向对象 开发语言

对话行业智能化先锋|宁夏大学:从300间未来教室迈向教育智能化

平平无奇爱好科技

Linux学习之Ubuntu 20使用systemd管理OpenResty服务

百度搜索:蓝易云

Linux ubuntu 运维 openresty systemd

基于 Amazon S3 Express One Zone 和 Amazon SageMaker 的图像分类模型实战—深析新旧产品突显 Express One Zone 在性能上的优势

亚马逊云科技 (Amazon Web Services)

AI板块的火热,现在参与Gensyn来得及吗?

币离海

AI Gensyn

如何做代币分析:以 USDT 币为例

Footprint Analytics

blockchain defi

巧用飞羽审批,实现业务起飞

平平无奇爱好科技

云服务器搭建网站全过程

百度搜索:蓝易云

云计算 Linux 运维 云服务器 ECS

揭秘商品计划管理系统:鞋服品牌如何实现飞跃式增长?

第七在线

已解决com.holonplatform.core.Validator.ValidationException校验异常的正确解决方法,亲测有效!!!

小明Java问道之路

OpenAI 视频生成模型发布,创作者如何利用 AI 工具最大化提升创作效率?

算法的秘密

释放心中的野兽

一跃皑皑

听到心声,看见变化——WeLink助力上海理工大学打造“校园12345服务平台”

平平无奇爱好科技

Java 包和 API 深度解析:组织代码,避免命名冲突

小万哥

Java 程序人生 编程语言 软件工程 后端开发

Base 链官方点名 $AYB,继续飙涨指日可待?

股市老人

质量保障体系的生命周期

老张

软件测试 质量保障

用WeLink连接每一位员工,加速打造“数字易立德”

平平无奇爱好科技

通过 Kong Gateway 性能基准和开源测试套件实现透明度和信任

Gingxing

kong API网关 Kong 网关 消息网关 Kong Gateway

PDF怎么转换成PPT文件?用这个AI在线转换工具,轻松搞定!

彭宏豪95

效率 职场 在线白板 办公软件 AIGC

苹果取消电动汽车项目;英伟达 CEO 黄仁勋寄语:学习编程价值大幅降低丨 RTE 开发者日报 Vol.153

声网

在追求科技进步的同时,如何避免通用人工智能带来的负面影响?

算法的秘密

密码学在 Web3 钱包中的应用:私钥是什么?bitget钱包为例

股市老人

预算有限,资源冗余?DWS集群缩容如何帮你解决烦劳

华为云开发者联盟

数据库 华为云 华为云开发者联盟 华为云GaussDB(DWS)

Treetop——基于Ruby的PEG解析器生成器_Ruby_Werner Schuster_InfoQ精选文章