写点什么

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:171679
用户头像

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

关注

评论

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

开源应用中心|动手自建一个超高度自由的个人知识库,原来这么容易!

开源

让 Serverless 应用开发更简单,Serverless Devs 2.0 全新发布

Serverless Devs

开源 Serverless

如何给技术部员工做考核?

石云升

团队管理 管理 引航计划 内容合集 9月日更

测试九剑之-破箭式

薛飞

自动化测试 测试管理

kube-ovn 组网结构

Geek_f24c45

k8s Kube-OVN cni

想要入职阿里P6?最少啃完这本500页Java并发多线程源码笔记

Java 编程 面试 多线程 阿里

【墨天轮专访第四期】华为云GaussDB苏光牛:发挥生态优势,培养应用型DBA

墨天轮

数据库 华为云 GaussDB

亚信科技AntDB数据库国产化进程加速,计费上云再下一城

亚信AntDB数据库

实践案例 9月日更

Chrome前端调试技巧分享

华为云数据库小助手

大前端 调试 GaussDB 华为云数据库

会员业务基于Cloud KMS的数据安全应用

爱奇艺技术产品团队

数据安全法 Cloud KMS

App 不想被“点名”,mPaaS 隐私合规检测为开发者护航数字生态建设

蚂蚁集团移动开发平台 mPaaS

移动开发 mPaaS 监管合规 隐私安全

Elasticsearch 原理解析(介绍)

ZzC🍖

搜索引擎 elasticsearch

数字化助力能源高效利用

CECBC

用诸葛孔明的智慧,读懂新型数据中心的“四新”机遇与产业逻辑

脑极体

守护油田安全,EMQ X 在石油石化危化品监测管理中的应用

EMQ映云科技

物联网平台 物联网 IoT 边云协同 emq

前端技术概览

数据库 大数据 时序数据库 tsdb 数据智能

流媒体:依托于声网的连麦解决方案

声网

音视频 流媒体

上线半天下载量破100W!美团大佬的Java性能调优实战手册,超详细

Java 编程 面试 性能调优

交易所刷量机器人定制开发案例(源码搭建)

量化系统19942438797

交易所 做市机器人 自动刷量机器人

联想新IT引擎引领智能化变革,助力“中国力量”更加强大

科技范儿

面对面小程序开源

OpenIM

低代码时代来临,织信Informat携手低码星球探讨「企业数字化转型之路」

优秀

低代码

阿里后端优化这么恐怖?看完这20W字Java性能实战经验手册,最少P7

Java 阿里巴巴 面试 性能调优 金九银十

浪潮云洲发布标识解析数据网关产品

工业互联网

京东云金秋上云特惠进行中!扫码参与活动

京东科技开发者

云计算 云主机 大促

北鲲云超算平台凝聚技术实力,赋能高算力需求行业加速发展

北鲲云

阿里官方保姆级Java技术图谱发布!够学到春节了,赶紧收藏!

Java 面试 阿里 大厂 金九银十

【SoCC2018论文】DAGOR:微信「大规模微服务过载控制系统」

OpenIM

GraphQL 快速入门【1】简介

码语者

Rest graphql

百度智能云开物工业互联网平台解决方案亮相2021服贸会成果发布会

百度大脑

人工智能 服贸会

【得物技术】浅谈重复http请求的取消

得物技术

方法 HTTP 场景 crud 请求

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