Magan is compromisation between static parser generator and dynamic parser combinator. We can call it a stanamic parser generator. The generator can be used in either static way, that is, generate efficient parsers based on the grammar file, or a dynamic way, that is, change part of the parser with normal ruby code.
The grammar file shares many aspects with regular expressions, so you don't have to do much to switch mind sets when you rewrite your regexps into a parser.
The compiled parser is essentially mostly (yet another) PEG parser. Rules are effectively compiled into ruby code and Onigmo regular expressions, which are compiled to bytecodes and are very fast (todo benchmarks to show how fast it is). In addition to the PEG thingies, Magan provides local look backwards, limited non-greedy quantifiers, back references, and helpers to make parser building a lot easier. Existing parsers can also be extracted and reused in a modulized way.
todo
They are similar to ruby strings. Single quoted string has less escape rules, and double quoted string can be interpolated and you can use many escapes.
hello = 'hello'
world = "world \u1234"
Char groups are the same as in Onigmo. For example, to match a char that can be a
, b
, c
or d
ranged_chars = [a-d]
You can use the double negation trick to exclude some char from a char group
alphabet_chars_except_w = [^w[^a-z]]
The whole list of backslashed, predefined char classes:
any_char_except_newline = .
word_char = \w
non_word_char = \W
digit_char = \d
non_digit_char = \D
hex_char = \h
non_hex_char = \H
space_char = \s
non_space_char = \S
Char groups and classes can be combined just as in Onigmo
a_or_digit_chars = [a\d]
Unicode char classes
chinese_chars = \p{Han}
any_char = \p{Any}
There are two little differences from Onigmo char classes. The first one is, POSIX bracket expressions are not supported yet because I'm too lazy. The second one is, you can write \p{Han,Hiragana}
instead of [\p{Han}\p{Hiragana}]
--- saving a bit writing, yay!
The same as regexp anchors
bol = ^
eol = $
begin_of_str = \A
end_of_str = \z
end_of_str_before_newline = \Z
word_boundary = \b
non_word_boundary = \B
\G
(matching start position) is not supported.
Capture variables are defined before a unit expression, and are used in blocks or back references.
Normal captures
var:expr1 var:expr2
In the above code, since two expressions share the same capture variable, the capture of rule2
just replaces the capture of rule1
.
Aggregate variables means the capture is put inside an array. For example, to collect repeated captures:
(aggregate_var::rule1 rule2)*
Here's a nonsense example that the rule hello_world
invokes the rules hello
and world
:
hello_world = hello ' ' world
hello = "hello"
world = "world"
As you can see in the example, rules are declarative, not neccesary to be decalared before used.
The syntax is much like back references in Onigmo, here's an example for matching strings that can either be single quoted or double quoted:
string = open:['"] ("\\" . / !\k<open>.)* \k<open>
Note: we use the term reference here in contrast to literal. A literal expression means it is fully composed without using any reference. For example, ("a"+"b"+)?
is a literal but a
is not.
We use the PEG notations here.
world = "world"
hello = "hello" &world
identifier = !\d \w+
Only available for expression of pure literals:
<&("a"+)
You can not put a reference inside a look backward, a compile error will be raised for the code below:
hello = "hello"
world = <&hello "world"
Also literals only:
we_are = <!\w \w+
We support the following possessive quantifiers for all grammar expressions. The term "possessive" means the repeat count is fixed for self-longest-match, won't backtrack for less repeat counts.
a+ # one or more a
a* # zero or more a
a? # zero or one a
They are the same as "greedy" quantifiers described in PEG papers, but we prefer the term "possessive" to distinguish them from the real "greedy" ones as described below.
A greedy quantifiers backtracks to maximize the match length for the literal chain it belongs to. The following greedy quantifiers are currently limited to be put after literals --- that is --- they can not be put after an expression containing any references.
'a'+* # one or more 'a', backtracks if consecutive literal pattern not match
# it backtracks from longest to shortest
'a'** # zero or more 'a'
'a'?* # zero or one 'a'
A reluctant quantifiers tries to repeat as less as they can, also limited to literals.
'a'+? # one or more 'a', backtracks if consecutive literal pattern not match
# it backtracks from shortest to longest
'a'*? # zero or more 'a'
'a'?? # zero or one 'a'
todo example for greedy / reluctant / possessive.
/
Every rule allows at most one block transformer wrapped between {
and }
.
To access environment in the block
ast # the whole abstract syntax tree
@src.filename
@src.pos
@src.line
@src.col
You have the responsibility to ensure the transformers idempotent --- which means for a certain position in the source code, the processor should return the same result no matter how many times it is called, and the side effects should not accumulate.
If you need a processor that is not idempotent, custom a helper.
By the way, please don't worry about nested braces or strings inside the block, the rule compiler is smart enough to recognize very complex ruby code.
Helpers are tools for building special or complex parsers from basic grammar expressions. Calling a helper looks like invoking a lambda in Ruby. We provide several helpers to help reduce the amount of work.
The following rule parses either 'a'
or 'A'
:
i['a']
The only argument of i[]
must be a literal.
Assume you want to parse arbitrary non-recurring permutations of a
, b
and c
, you may write a very complex rule like this:
a \s+ (b \s+ c / c \s+ b) / b \s+ (a \s+ c / c \s+ a) / c \s+ (a \s+ b / b \s+ a) / a (\s+ (b / c))? / b (\s+ (a / c))? / c (\s+ (a / b))?
These surely will explode if you add one more reference d
! Or you may give up and use a simpler rule and a block to reject the repeated ones?
x:(a / b / c)+ { throw :reject if x.uniq != x; x }
Or you can just use the permutations[]
macro for the dirty job:
permutations[a, b, c, \s+]
It's very handy for parsing weird syntaces like Java method modifiers synchronized public static wtf
!
Indentations are hard to fit in PEG syntax (they can not be cached, and a rule starting with indent / dedent / samedent can neither be cached). With the assumption that a rule not starting with indents is not affect by indent rules, we have helpers for this job:
indent[]
dedent[]
samedent[]
TODO: explain details and other indentation helpers
Similar to scanf, the AST is a string node and the paresd value is converted.
scanf['the address %x stores the floating number %f']
Similar to unpack, the AST is a string node and the parsed value is converted.
unpack['qqI']
You can customize your helpers too. For example, if you have a close
helper implemented like this:
class MyParser
include Magan
grammar File.read('a_syntax.magan')
helper[:close] = -> backref_parser {
# Note that a helper is a transformer for rules instead of results
# if you want to transform results, use `map`
backref_parser.map do |res|
'(' => ')',
'[' => ']',
'{' => '}',
'|' => '|',
'<' => '>'
end
}
compile :main
end
You can use it like this:
expr = x:[\(\[\{\|\<] content close[\k<x>]
Helper generated parsers are not cached by default, so you can apply dynamic non-idempotent logic here if you want. For example, to count how many times the parser is applied:
helper[:count] = -> parser {
parser.map do |res|
@count ||= 0
@count += 1
res
end
}
Each rule is parsed into a method, parse_xxx
, and the trace will guide you
It's important to know what and how the parser does so we can tweak the grammar.
todo: Annotated source and expectations for unit testing
todo
todo
Change rule AST and re-generate new parsers.
todo
sell point, good for syntax coloring. todo
todo
todo add simple examples inside this guide
todo
Because:
- Even the simplest internal DSL is a bit too verbose to show what the grammar does.
- Internal DSL is hard to make rules declarative.
- With internal DSL you have to modify symbols to fit host grammar.
- Grammar definition can be used to generate targets in other languages.
todo report error at sight of left recursion
todo experiment limited left recursion support
You know, with PEG you can not use a lexer to just drop out the spaces. My trick is to define _
as "\s"*
or [\t\ ]*
, looks a bit cleaner.
My trick is to embed comment rules inside space rules and end-of-line rules. Example for skipping C++ style comments:
eol = line_comment | $
_ = join[\s*, block_comment | eol]
line_comment = "//" .* $
block_comment = "/*" [.\n]*? "*/"
There's already proof that if we disambiguate LL(k) grammar in a certain way, it can be transformed into a PEG grammar.
But another question is, can PEG express something that's not CFG? Sure! Remember the unlimited look forward!
The example context sensitive language is L = {a^nb^nc^n | n>0}
. It can not be described with context free grammar, thus not able to be parsed by pure CFG methods. But it can be described with our PEG:
l = &(x 'c') 'a'+ y
x = 'a' x* 'b'
y = 'b' y* 'c'
It's common misunderstanding that regexp engines are weaker than parser generators, in fact, regexps are weaker but regexp engines are not! A modern regexp engine (except re2, which sacricfices power for speed) has named groups and capable of parsing recursive rules, and there's research that found it impossible to convert many constructs like back references into PEG. While PEG rules can be easily converted into Onigmo regexp, as Magan does.
The only weakness of Onigmo is, it's hard to debug into the matching process, fixing this weakness is one goal of Magan.
The result AST is array of arbitry levels, the leaf elements are purely strings. You may use Array#join
to restore the text.
The parser supports caching, you can choose totally caching or only cache the results larger than a certain length. The caching based on length is has benefits of memory and time.
You have to double backslashes if using double quotes. For example:
class ExampleGrammar
include Magan
grammar "nbsp = [\\ \\t]*"
compile :nbsp
end
The single quote form %q|...|
plays best with our grammar:
class ArithmeticGrammar
include Magan
grammar %q|
expr = _ add _
int = '-'? \d+
atom = '(' _ expr _ ')' / int
mul = atom (_ [*/] _ atom)*
add = mul (_ [+-] _ mul)*
_ = [\ \t]*
|
compile :expr
end
BSD, see copying
Parslet, Parsley, PEG.js and lots of people working on parser theories.