UPDATE: Slides and video from my talk on this topic In this series, we’ll look at how so-called “applicative parsers” work. In order to understand something, there’s nothing like building it for yourself, and so we’ll create a basic parser library from scratch, and then some useful “parser combinators”, and then finish off by building a complete JSON parser. Now terms like “applicative parsers” an
pest is a general purpose parser written in Rust with a focus on accessibility, correctness, and performance. It uses parsing expression grammars (or PEG) as input, which are similar in spirit to regular expressions, but which offer the enhanced expressivity needed to parse complex languages. Accessibility Grammar-generated parsers are both easier to use and maintain than their hand-written counte
I’ve been exploring various ways to write parsers. For a long time, I’ve used hand-written recursive descent for its straightforwardness, flexibility, and performance. There is another way—parser generators like Menhir, LALRPOP, or the venerable Bison use the bottom-up LR algorithm. While LR parser generators have several nice properties—using the grammar directly as the parser’s source code, auto
Writing parsers like it is 2017 Pierre Chifflier Agence Nationale de la Sécurité des Systèmes d’Information Geoffroy Couprie Clever Cloud Abstract—Despite being known since a long time, memory violations are still a very important cause of security problems in low-level programming languages containing data parsers. We address this problem by proposing a pragmatic solution to fix not only bugs, b
yacc/lexとは Cでプログラミング言語の処理系を実装するのであれば、 多くの場合、yaccとlexというツールを使います。 実のところ、Cとyacc/lexで簡単なプログラミング言語を作る、というのは、 以前、「C言語ヨタ話 」で書いた「 電卓を作ってみよう」 の焼き直しになります。yaccとlexの説明もそちらに簡単に書いたので、 そちらを見てください――と言いたいところですが、 まあここでも軽く説明します。 内容的には重複、というかコピペしている部分もありますが。 プログラミング言語の処理系は、通常、以下のような手順を取ります。 字句解析 ソースプログラムを、「字句(トークン)」の並びに分割する処理です。 構文解析 トークンの並びから、解析木を構築する処理です。 この後、Cなどの機械語を吐くコンパイラや Javaのようなバイトコードを吐くコンパイラなら、 「コード生成」という処理
My first adventures in parsing theory came when I was doing an independent study of programming languages in college. When I got to the part about algorithms such as LL, LR, and their many variations (Strong-LL, SLR, LALR, etc), I was fascinated. I felt like I was peering at some deep and powerful incantations, the significance of which I could not yet appreciate, but I was sure that someday terms
Parsing structured text into data structures has always been a pain. If you are like me, you may have wondered: why do all the parsing tools seem to be parser-generators instead of just configurable-parsers? After all, when you look at, say, a 2D physics library like Chipmunk2D, you just get a bunch of classes and functions you can call. In contrast, parsing libraries like YACC or ANTLR often seem
概要 Supership株式会社インフラ事業開発本部・検索グループで11月から (2016年4月よりサービス事業本部 Syn.事業部 検索サービス部に改組) エンジニアとしてジョインした@ShingoOKAWAです。 弊社検索グループでは、KDDIグループのハウスエージェンシーとしてのauポータルサイトの検索サービスの開発や、その他自社で提供するサービス・プロダクトの種々の検索機能の開発業務に取り組んでいます。 『Elasticsearch Advent Calendar 2015』に投稿させて頂いたことからもお分かりかと思いますが、バックエンドの検索エンジンは Elasticsearch を採用しております。検索サービスの拡充及び改善のため、日々開発業務に取り組んでいるわけですが、本投稿では、その中でも弊社バックエンドのコア機能として開発中の『Domain Specific Query
はじめに 近頃、Scala界隈で注目を集めているパーザコンビネータライブラリに fastparseがあります。このfastparse、Scala標準のパーザコンビネータライブラリ(scala-parser-combinators)より、なんとものによっては100倍速いとのことです。ちょうど、Scala 2.11でscala-parser-combinatorsが別ライブラリに分離されたところだったので、もっと良いライブラリがないかと考えていたところだったので、早速試してみることにしました。 ちなみに、はてなブログの記事入門fastparse(1) ～四則演算評価器を作ってみた～では入門と書いているものの自分が入門してみたという内容ですが、このエントリでは他に人にとっても入門となるように（一応）書いてみたつもりです。 準備作業 fastparseを導入するには、build.sbtに以下の行を
FastParse 2.2.2 Fast to write, Fast running Parsers in Scala import fastparse._, NoWhitespace._ def number[_: P]: P[Int] = P( CharIn("0-9").rep(1).!.map(_.toInt) ) def parens[_: P]: P[Int] = P( "(" ~/ addSub ~ ")" ) def factor[_: P]: P[Int] = P( number | parens ) def divMul[_: P]: P[Int] = P( factor ~ (CharIn("*/").! ~/ factor).rep ).map(eval) def addSub[_: P]: P[Int] = P( divMul ~ (CharIn("+\\-")
Multiple items val string : value:'T -> string Full name: Microsoft.FSharp.Core.Operators.string -------------------- type string = System.String Full name: Microsoft.FSharp.Core.string Multiple items val int : value:'T -> int (requires member op_Explicit) Full name: Microsoft.FSharp.Core.Operators.int -------------------- type int = int32 Full name: Microsoft.FSharp.Core.int --------------------
Introduction Parsing expression grammars (PEGs) are an alternative to context free grammars for formally specifying syntax, and packrat parsers are parsers for PEGs that operate in guaranteed linear time through the use of memoization. For a brief technical summary see the Wikipedia entry on PEGs. For more in-depth descriptions see the original PEG paper and packrat parsing paper, and related pape
Introduction: Writing Parser Imperatively Parsing CSV: Imperative Lexer Parsing HTML: Parsing Stack Expression: Operator Precedence Based Parsing REPL, Brackets, and Variables Statement: Top-down Context Based Parsing Full Javascript Parser - Abstract Syntax Tree An abstract syntax tree (AST) is a term in computer science for a tree structure representing the syntactic structure of a source code.
「ふつうのHaskellプログラミング」や 「構文解析結合子」の元ネタは、どうやら「Monadic parsing in Haskell」のようです。(さらに元ネタは Parsec ですかね。) このオリジナルは、MonadPlus の部分などが古くさいのですが、分りやすいです。というわけで、例題を Parsec 風にアレンジしつつ、勉強してみました。 四則演算式のパーサーを実現することを目標にします。 おまじない 最終的に以下のモジュールが必要になるので、import しておきます。 import Monad import Data.Char Parser の定義 Parser 型の定義はこうなります。 data Parser a = Parser (String -> [(a,String)]) 状態を表すために関数を使っている 関数を使うと状態が表現できることが分らない人は、先に「状
パーサーに関して、調べたことと疑問を書いておきます。パーサーに詳しい人に答えて頂けると、とても嬉しいです。 チョムスキー階層によれば、以下のような関係が成り立ちます。 正規文法 < 文脈自由文法 < 文脈依存文法 < 制限のない文法 それで、文脈自由文法の中は、こういう関係が成り立ちます。 LL法 < SL法 < LALR法 < LR法 < GLR法 GLR法は、文脈自由文法の全体を解析できる能力を持ちます。 疑問1) GLR法は、文脈依存文法(の一部)も解析できるのか？ LL(1) LL(1)に、収まっているのは XML や Lisp です。 LALR(1) LALR(1)に、収まっているのは、ほとんどのコンピュータ言語です。たとえば、C や Java。 GLR GLRに収まっているのは、C++ です。たとえば、D 言語の「テンプレート再訪」には、以下のように文脈がないと比較なのかテンプ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
