プログラミング言語の実装に欠かせない構文解析、なかでもとりわけLR構文解析とLR parserに注目した本です。 一冊まるまるLR構文解析とLR parserに関する内容となっており、LL構文解析などの他の手法についてはまったく触れていません。 本書は2つの章からなります。 第1章はLR parserの概論です。 * 簡単な文法と複雑な文法を例に、それぞれのparserの動きを考察する"LR parserの仕組み" * 与えられた文法定義からLR parserを構成する"LR parserの構成方法 " * SLR, Canonical LR, LALRといった様々なLR parserの特徴を紹介する"LR parserの種類" といった内容を取り上げます。 第2章は「Efficient computation of LALR(1) look-ahead sets」という論文の解説です。
こんにちはかねこです。私はCRuby(ruby/ruby)のコミッタをやっているのですが、最近はCRubyをメインのターゲットとしてLALR parser generator Lramaの開発をしています。 現役のLALR parser generator開発者として、日頃私以上にLR parserのことを考えている人はそうはいないでしょう。 この記事を読んでいる皆さんは構文解析、なかでも特にLR parserを理解するためにいろいろな教科書や記事を読んできたと思います。 一方でどんなに調べてもどこか腑に落ちない部分が残っているのではないでしょうか。 LR構文解析を勉強すると構文解析表に出会うとおもいます。 構文解析表を作る方法そのものは教科書に説明が載っており、その通りに手を動かせばこのような表を作ることはできるでしょう。 また出来上がった構文解析表をもとに実際に構文解析する手順も理解で
パーサ・ジェネレータとは 少し複雑な文法 四則（加減乗除）計算のBNF Racc で実装 クラス定義、BNFの記述部分 ヘッダー、インナー、フッター コンパイルと実行 演算子の優先順位と結合における左右の優先順位 まとめ パーサ・ジェネレータとは パーサを日本語で「構文解析器」といいます。 「器」とといっても、「うつわ」ではなく「器械」、より適切にはアプリケーションまたはプログラムのことです。 つまり、構文解析をするプログラムです。 「構文解析」とは、「プログラム言語などの構文」を「解析」することです。 簡単な例として、足し算を考えてみましょう。 1+2 11+34 123+456 3つの足し算の例があります。 出てくる数字は違うものですが、どれも「数字＋数字」というパターンは変わりません。 3番めの文字列は7つの文字からなっています。 1, 2, 3, +, 4, 5, 6 この7文字は
8/19に開催されたRubyKaigi 2023 follow upで、Rubyのparserとparser generatorに関する進捗と今後の方針について話をしてきました。 rhc.connpass.com 当日の資料はこちらにアップロードしてあります。 speakerdeck.com 進捗とこれからの話 RubyKaigiでの発表を踏まえて3つの点についてRubyKaigiからの進捗とこれからの話をしました。 Error-tolerant Universal Parser Maintainability Lramaとは github.com RubyでかかれたLALR parser generatorです。BNFをベースにしたDSL(parse.y)を受け取って、C言語実装のLALR parserを生成します。現在のCRubyはLramaが生成したparserを使用しています。 E
2023年6月15日に『深掘りRubyKaigi 2023 with spikeolaf & makenowjust』を開催しました。イベントの内容をほぼ全文文字起こし形式でお届けします。この記事は第2部です。 hey.connpass.com 登場人物 ゲスト makenowjust/藤浪 大弥さん spikeolaf/金子 雄一郎さん STORES fujimura/藤村 大介 shyouhei/卜部 昌平 hogelog/小室 直 パーサとの出会い fujimura：金子さんのパートにいきます。簡単にどんな話をRubyKaigi 2023でしたか紹介していただけますでしょうか？ spikeolaf：ここ2年ぐらい、主にAnd the WorldっていうRubyKaigiの名物コンテンツを見ていると、パーサへの関心というのは高まってきていて、ここ何年かで何が問題かはだいぶ整理されてきて
概要 原著者の許諾を得て翻訳・公開いたします。 英語記事: Rewriting the Ruby parser | Rails at Scale 原文公開日: 2023/06/12 原著者: Kevin Newton サイト: Rails at Scale | The Ruby and Rails Infrastructure team at Shopify exists to help ensure that Ruby and Rails are 100-year tools that will continue to merit being our toolchain of choice. CC BY-NC-SA 4.0 Deed | 表示 - 非営利 - 継承 4.0 国際 | Creative Commons 日本語タイトルは内容に即したものにしました。 なお、本記事では「パーサー
Parser generators vs. handwritten parsers: surveying major language implementations in 2021 Developers often think parser generators are the sole legit way to build programming language frontends, possibly because compiler courses in university teach lex/yacc variants. But do any modern programming languages actually use parser generators anymore? To find out, this post presents a non-definitive s
At Shopify, we have spent the last year writing a new Ruby parser, which we’ve called YARP (Yet Another Ruby Parser). As of the date of this post, YARP can parse a semantically equivalent syntax tree to Ruby 3.3 on every Ruby file in Shopify’s main codebase, GitHub’s main codebase, CRuby, and the 100 most popular gems downloaded from rubygems.org. We recently got approval to merge this work into C
前回のあらすじ Ruby Parser開発日誌 (7) - doについて考える - かねこにっき Rubyのdoのもつ複雑さを中心にMaintainabilityの改善方法について考えました。Practical LR Parser Generationで紹介されているNonterminal attributesというアプローチにprecedence(優先度)をさらに組み合わせることで、lexerの状態として管理しているものを構文に組み込むことに成功したのでした。 ところでRuby Committers vs The Worldの2022や2021をあらためてみると、おもに次の3つが解くべき問題だと言われています。 Usability (Error-tolerant parser) Maintainability Universal Parser 1と2についてはすでに分析と実装をしてきまし
前回のあらすじ Ruby Parser開発日誌 (5) - Lrama LALR (1) parser generatorを実装した - かねこにっき Error Recoveryを実装するためにLrama LALR (1) parser generatorを実装しました。 Error Recoveryについては目処がたったので今回はparse.yのMaintainabilityをいかにして改善するか考えたいと思います。 parse.yの難しさ Rubyのparse.yの難しさについては聞く人によって異なる回答が返ってくるところですが、おおよそ以下のようにまとめることができると思います。 ファイルの行数が多い shift/reduce conflictやreduce/reduce conflict時に何が起きているか分かりにくい Bisonが原始的な記法しか提供していないので全ての規則を書
前回のあらすじ Ruby Parser開発日誌 (4) - かねこにっき Error Recoveryに関する理解も深まり、Rubyのparserへ実装するために3つの実装方法を検討しましたが、どれもあまり簡単な方法ではありませんでした。この問題を解決するためにLALR parser generatorを実装したので今回はその紹介をしたいとおもいます。 Lrama LALR (1) parser generator github.com 前回検討したとおりBisonを使ってError RecoveryをRubyに実装していくのは困難を伴います。これを解決するために自前でparser generatorを実装し、generatorおよびtemplateの両方を自分で管理するという方法を思いついたので実装しました。 名前の由来 Lramaでリャマと読みます。LALR parser genera
コンパイラの構文解析器に広く使用されているLR構文解析の原理を解説する．LR構文解析の基礎をなすアイデアは，「正規言語の解析手法を繰り返し使い，文脈自由文法の幅広いクラスを解析する」という(多くの優れたアイデアがそうであるように)単純なものである．Knuthは，この直感的で単純なアイデアを基礎とし，緻密な理論的な展開と巧みな実用化戦略によって，構文解析におけるブレークスルーを達成した．本解説では，LR構文解析が基礎とするアイデアに即してその原理とアルゴリズムの構造を解説する．これらを理解するならば，一般に複雑で難解なものと受け取られているLR構文解析法の全体像が容易に理解できるはずである．本解説では，オートマトンの基礎知識を持つ一般の読者が，LR構文解析の考え方と原理を理解できることを目指す．
Error Tolerant parserに関するアイデア 9月半ばに行われたRubyKaigi 2022以来、3ヶ月くらいError Tolerant parserについて調べたり考えたり実装をしたりしています。 途中でもいいからなにかにアウトプットしておくとよいというアドバイスをもらったので、今現在の状況や考えていることを書いておこうと思います。 Error Tolerant parserとは? どうしてそれが欲しいの? 通常parserはユーザーの入力を受け取り その入力がそのプログラミング言語にとって、validなものか否かをチェック validな場合、その後の工程にとって都合のいいデータ構造(例えばAST)に変換し、後工程に渡す invalidな場合、Syntax Errorをレポートする といった処理を行います。 しかしIDEやLSP(Language Server Proto
rubykaigi.org Rubyのパーサーを書き直そうという野心的なプロジェクトを持っている人の発表です。 プロジェクトに対するモチベーションに関してはこちらのツイートのスレッドを見るのがよいと思います。 Since @yukihiro_matz mentioned it on stage at #rubykaigi... Yes! I'm going to be rewriting the Ruby parser. I'm super super excited about this, and you should be too! Below is a brief thread about how and why, but tl;dr: portability, error tolerance, and maintainability.— Kevin Newton (@kddnewt
Sorry, this post will read like a “dear diary” entry rather than some life-changing HN-worthy guidance. Back in November 2020, almost on a whim I started work on a new parser for the Ruby programming language. It was almost exactly a year after I had started working on my compiler project (I hope to write a longer post about that someday soon), and in my frustration with the state of affairs with
The Lezer Parser System The problem of parsing structured text has resisted one-size-fits all solutions for over 60 years. Lezer isn't such a solution either, but it is a very decent parser generator, especially well suited for use in code editors. Lezer (the Dutch word for reader, pronounced like “laser”) provides a parser generator that outputs JavaScript modules, which can be loaded to parse co
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く