TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

LL and LR Parsing Demystified (2013)

155 点作者 implmentor超过 8 年前

7 条评论

AceJohnny2超过 8 年前
What about Earley&#x27;s algorithm?<p><i>Unfortunately, given the extremely limited hardware of 1960s computers (not helped by the lack of an efficient algorithm), the parsing of an arbitrary CFG was too slow to be practical. Parsing algorithms such as LL, LR, and LALR identified subsets of the full class of CFGs that could be efficiently parsed. Later, relatively practical algorithms for parsing any CFG appeared, most notably Earley&#x27;s 1973 parsing algorithm. It is easy to overlook the relative difference in performance between then and now: the fastest computer in the world from 1964-1969 was the CDC6600 which executed at around 10 MIPS; my 2010 mobile phone has a processor which runs at over 2000 MIPS. By the time computers had become fast enough for Earley&#x27;s algorithm, LL, LR, and friends had established a cultural dominance which is only now being seriously challenged - many of the most widely used tools still use those algorithms (or variants) for parsing. Nevertheless in tools such as ACCENT &#x2F; ENTIRE and recent versions of bison, one has access to performant parsers which can parse any CFG, if that is needed.</i><p>from: <a href="http:&#x2F;&#x2F;tratt.net&#x2F;laurie&#x2F;blog&#x2F;entries&#x2F;parsing_the_solved_problem_that_isnt.html" rel="nofollow">http:&#x2F;&#x2F;tratt.net&#x2F;laurie&#x2F;blog&#x2F;entries&#x2F;parsing_the_solved_prob...</a><p>Featured here 6 years ago: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=2327313" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=2327313</a>
评论 #12554183 未加载
haberman超过 8 年前
Happy to see this show up here again. It&#x27;s one of my articles that I&#x27;m most proud of.<p>I&#x27;m happy to answer any questions about it.
评论 #12553092 未加载
评论 #12556729 未加载
nickpsecurity超过 8 年前
People interested in these things should look up GLR and GLL. Pretty powerful when I studied them.
评论 #12554226 未加载
评论 #12555257 未加载
CalChris超过 8 年前
tl;dr use ANTLR<p>But actually, I did read this excellent article for the second time. However, unless you are skilled in the art, you should be using ANTLR4, Honey Badger. Terence Parr deserves a Turing award.<p>For parsing, most upper div compiler classes start off with CFGs, dip briefly into LL recursive descent and then conclude with LALR. If people remember anything, it&#x27;s SHIFT&#x2F;REDUCE. Unfortunately, there doesn&#x27;t seem to be any standard tools for the LL(1) equivalent, FIRST&#x2F;FOLLOW tables. And as the article shows, they aren&#x27;t equivalent. Each has strengths but LALR has tools.<p>Except for ANTLR. Which started out as recursive descent ...<p>Parsing Techniques doesn&#x27;t really have any competition. The compiler books, like the compiler classes, can only give a little attention to parsing. Given how strong the available tools are and how hard the remaining subjects are (SSA, code generation, ...) maybe they have a point.
评论 #12555794 未加载
评论 #12554666 未加载
cjhdev超过 8 年前
I&#x27;ve learned a lot about LALR and GLR using Bison in combination with Ruby.<p>Bison and Flex are available as apt packages on Ubuntu and there is heaps of documentation.<p>The Ruby angle means you don&#x27;t have to roll your own AST structures. Also, Ruby&#x27;s &#x27;VALUE&#x27; type is easily passed around in Bison grammar.<p>example:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;cjhdev&#x2F;slow_blink&#x2F;blob&#x2F;master&#x2F;etc&#x2F;slow_blink&#x2F;ext_schema_parser&#x2F;parser.y" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;cjhdev&#x2F;slow_blink&#x2F;blob&#x2F;master&#x2F;etc&#x2F;slow_bl...</a>
viebel超过 8 年前
I&#x27;ve copy&#x2F;pasted the code of your reverse polish evaluator in python in this interactive blog post: <a href="http:&#x2F;&#x2F;blog.klipse.tech&#x2F;python&#x2F;2016&#x2F;09&#x2F;22&#x2F;python-reverse-polish-evaluator.html" rel="nofollow">http:&#x2F;&#x2F;blog.klipse.tech&#x2F;python&#x2F;2016&#x2F;09&#x2F;22&#x2F;python-reverse-pol...</a>
dream-on超过 8 年前
I fail to see the mystery. In my opinion, state machines are the most straight-forward parts of programming.<p>There is a learning curve with lex and yacc but if you cannot ever use these programs then what can you really call yourself a programmer?<p>It&#x27;s the endless search for a &quot;new&quot; programming language and the layers upon layers of needless abstraction created by today&#x27;s &quot;programmers&quot; that I find mystifying.
评论 #12556856 未加载