Stack Overflow
Stack Overflow

Questions tagged [peg]

A “Parsing Expression Grammar” (“PEG”) is a formal language to describe formal languages.

A Parsing Expression Grammar (“PEG”) is a formal language that defines a set of rules to describe a certain class of formal languages similar to context-free grammars.

In comparison to context-free grammars, PEGs have the advantage of always being unambiguous, and of mapping naturally to recursive descent parsers, which makes them easy to implement.

288 questions
40
votes
3 answers

What are the differences between PEGs and CFGs?

From this wikipedia page: The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered. If the first alternative succeeds, the second alternative is ignored. Thus…
Frankie Ribery
  • 11,933
  • 14
  • 50
  • 64
35
votes
5 answers

PEG for Python style indentation

How would you write a Parsing Expression Grammar in any of the following Parser Generators (PEG.js, Citrus, Treetop) which can handle Python/Haskell/CoffeScript style indentation: Examples of a not-yet-existing programming language: square x = x…
Matt
  • 17,290
  • 7
  • 57
  • 71
21
votes
1 answer

Ignore whitespace with PEG.js

I want to ignore whitespaces and new lines with my grammar so they are missing in the PEG.js output. Also, a literal within brackets should be returned in a new array. Grammar start = 'a'? sep+ ('cat'/'dog') sep* '(' sep* stmt_list sep*…
Matthias
  • 7,432
  • 6
  • 55
  • 88
21
votes
3 answers

Simple parsing questions using PEG.js

I'm trying to wrap my head around PEG by entering simple grammars into the PEG.js playground. Example 1: Input: "abcdef1234567ghijklmn8901opqrs" Desired output: ["abcdef", "1234567", "ghijklmn", "8901", "opqrs"] Actual output: ["abcdef",…
Nick Evans
  • 211
  • 2
  • 3
18
votes
2 answers

Performance of parsers: PEG vs LALR(1) or LL(k)

I've seen some claims that optimized PEG parsers in general cannot be faster than optimized LALR(1) or LL(k) parsers. (Of course, performance of parsing would depend on a particular grammar.) I'd like to know if there are any specific limitations of…
Roman Boiko
  • 3,576
  • 1
  • 25
  • 41
17
votes
2 answers

Join is not a function

I'm playing around with PEG.js start = keyword keyword = a:[a-z]? {return a.join("");} Why am I getting here the error: a.join is not a function when I enter a valid string like abc?
Evgenij Reznik
  • 17,916
  • 39
  • 104
  • 181
17
votes
1 answer

Generate TextMate language grammar from PEG.js grammar

Is there a tool that translates a PEG.js grammar to a TextMate grammar? I am building my own language and would like to have syntax highlighting for it in my preferred editor, TextMate. The grammar of my language is built with PEG.js. According to…
Manuel Leuenberger
  • 2,327
  • 3
  • 21
  • 27
15
votes
2 answers

Limitations of PEG grammar & parser generators?

I was enjoying using YARD a lot: http://www.ootl.org/yard/ http://code.google.com/p/yardparser/ http://www.codeproject.com/KB/recipes/yard-tokenizer.aspx I was able to construct fully functional calculator. I'm evaluating YARD to do PHP parser.…
Viet
  • 17,944
  • 33
  • 103
  • 135
14
votes
1 answer

Why is Parsimonious rejecting my input with an IncompleteParseError?

I've been trying to work out the basic skeleton for a language I've been designing, and I'm attempting to use Parsimonious to do the parsing for me. As of right now, I've, declared the following grammar: grammar = Grammar( """ program =…
Ethan Bierlein
  • 3,353
  • 4
  • 28
  • 42
13
votes
2 answers

CFG / PEG used for Code completion?

I'm wondering if it's possible to use a CFG or PEG grammar as a basis for code completion directly without modification. I have heard that code completion is in IDE's is sometimes manipulated and massaged or even hard coded so that it performs…
BefittingTheorem
  • 10,459
  • 15
  • 69
  • 96
13
votes
2 answers

How do you build a left-associative operator tree using PEG.js?

How do you build an AST (Abstract Syntax Tree) for left-associative operators using PEG.js? I've tried to write some code based on the information I found on the internet, but I seem to have made a mistake. The code I wrote generates an incorrect…
Toothbrush
  • 2,080
  • 24
  • 33
12
votes
2 answers

Parse indentation level with PEG.js

I have essentially the same question as PEG for Python style indentation, but I'd like to get a little more direction regarding this answer. The answer successfully generates an array of strings that are each line of input with 'INDENT' and 'DEDENT'…
Trevor Dixon
  • 23,216
  • 12
  • 72
  • 109
12
votes
2 answers

PEG and whitespace/comments

I have some experience writing parsers with ANTLR and I am trying (for self-education :) ) to port one of them to PEG (Parsing Expression Grammar). As I am trying to get a feel for the idea, one thing strikes me as cumbersome, to the degree that I…
Krumelur
  • 31,081
  • 7
  • 77
  • 119
11
votes
2 answers

How does backtracking work in peg.js (with example)?

I've defined the following minimal Peg.js grammar: start = "A1" / "A123" which you can try in the sandbox. I would have expected to match "A1" as well as "A123" (according to my notion of how backtracking works). But this is not the case: the…
Bosh
  • 8,138
  • 11
  • 51
  • 77
9
votes
2 answers

PEG.js - how to parse c-style comments?

Implementing a peg.js based parser, I get stuck adding code to to handle c-style comments /* like this */. I need to find the end marker without eating it. this not working: multi = '/*' .* '*/' The message is: line: 14 Expected "*/" or any…
Gisela
  • 1,194
  • 2
  • 16
  • 30
1
2 3
…
19 20