3 releases
0.1.2 | Feb 13, 2022 |
---|---|
0.1.1 | Feb 13, 2022 |
0.1.0 | Feb 13, 2022 |
#90 in #combinator
Used in floaout
100KB
2.5K
SLoC
Minimal Parsing Language (MPL)
This is minimal parser combinator of Minimal Parsing Language (MPL) like Top-Down Parsing Language (TDPL). It creates a abstract syntax tree (AST) for each input.
Getting Started
- implement
Variable
- insert each rule into
HashMap
minimal_parse()
- Optional
- implement
Input
- supports
[T]
andstr
by default
- supports
- implement
Position
- supports
u*
,i*
, andf*
by default
- supports
- implement
Span
- supports
StartAndLenSpan
by default
- supports
- implement
Terminal
- supports
SliceTerminal
,StrTerminal
, andU8SliceTerminal
by default
- supports
- implement
Output
- supports
()
by default
- supports
- implement
Rules
- supports
HashMap
by default
- supports
- implement
Parse
- supports
[T]
,str
, and[u8]
by default
- supports
- implement
Example
use crate::ParenthesesVariable::*;
use mpl::parser::Parser;
use mpl::rules::{RightRule, RightRuleKind::*, Rules};
use mpl::span::{StartAndLenSpan, Start, Len};
use mpl::output::Output;
use mpl::symbols::{StrTerminal, StrTerminal::*, Variable};
use mpl::trees::AST;
use std::collections::HashMap;
#[derive(Clone, Debug, Hash, Eq, PartialEq)]
enum ParenthesesVariable {
Open,
Parentheses,
Close,
}
impl Variable for ParenthesesVariable {}
struct ParenthesesParser;
impl<'i, V, P, L, R, O> Parser<'i, str, StrTerminal<'i>, V, StartAndLenSpan<P, L>, P, R, O>
for ParenthesesParser
where
V: Variable,
P: Start<str, L>,
L: Len<str, P>,
R: Rules<StrTerminal<'i>, V>,
O: Output<'i, str, V, StartAndLenSpan<P, L>>,
{
}
/// ```
/// Open = '(' Parentheses / ()
/// Parentheses = Open Close / f
/// Close = ")" Open / f
/// ```
fn main() {
let parser = ParenthesesParser;
let mut rules = HashMap::new();
rules.insert(
Open,
RightRule::from_right_rule_kind((T(Char('(')), V(Parentheses)), Empty),
);
rules.insert(
Parentheses,
RightRule::from_right_rule_kind((V(Open), V(Close)), Failure),
);
rules.insert(
Close,
RightRule::from_right_rule_kind((T(Str(")")), V(Open)), Failure),
);
let input = "(()(()))";
// all of the span
let all_of_the_span = StartAndLenSpan::<u32, u16>::from_start_len(0, input.len() as u16);
let result: Result<
AST<ParenthesesVariable, StartAndLenSpan<u32, u16>, ()>,
AST<ParenthesesVariable, StartAndLenSpan<u32, u16>, ()>,
> = parser.parse(input, &rules, &Open, &all_of_the_span);
if let Ok(ast) = result {
println!("{}", ast);
}
}
Test Examples
Parsers written with MPL
- WAV AST : RIFF waveform Audio Format
MPL
Definition of MPL grammar
A MPL grammar G
is a tuple G = (V, Σ, R, S)
in which:
V
is a finite set of variables.Σ
is a finite set of original terminal symbols.T
is an union ofΣ
orM
(Σ ∪ M) (M
(= {(), f}) is a finite set of metasymbols).R
is a finite set of rules of the formA = B C / D
A in V (A ∈ V),
B, C, D in E (E = T ∪ V) (T ∩ V = ∅) (B, C, D ∈ E).
For any variable A there is exactly one rule with A to the left of=
.
- S in V (S ∈ V) is the start variable.
Empty
()
is a metasymbol that always succeeds without consuming input.
Empty = () () / ()
Failure
f
is a metasymbol that always fails without consuming input.
Failure = f f / f
Extended MPL
Since one of the goals of MPL is to create an AST, it also supports two features in terms of ease of use and speed.
Any
?
is a metasymbol representing any single input like wildcard character. This succeeds if there is any input left, and fails if there is no input left.
Any = ? () / f
To extend the difinition of MPL grammar, let ? ∈ M.
All
*
is a metasymbol representing All remaining input like wildcard character. This will succeed even if the remaining inputs are zero.
All = * () / f
Same as All = ? All / ()
.
To extend the difinition of MPL grammar, let * ∈ M.
Difference between TDPL and MPL
The biggest difference between the two grammars is the rule form. There are two rule forms in TDPL.
A..BC/D
, A,B,C,D in V.
A..a
, a in ∑ ∪ {ε, f}, f is a metasymbol not in ∑ and ε is the null string.
MPL, on the other hand, has one rule form.
MPLG (MPL Grammar) syntax
In MPL grammar
// Hierarchical syntax
Mplg = ZeroOrMoreLines () / f
ZeroOrMoreLines = Line ZeroOrMoreLines / ()
Line = Line1 EndOfLine / f
Line1 = LineComment () / Line2
Line2 = Rule () / ()
Rule = Variable Rule1 / f
Rule1 = " = " Rule2 / f
Rule2 = E Rule3 / f
Rule3 = Space Rule4 / f
Rule4 = E Rule5 / f
Rule5 = " / " Rule6 / f
Rule6 = E () / f
E = TerminalSymbol () / Variable
// Lexical syntax
// Variable
Variable = Identifier () / f
// Terminal symbol
TerminalSymbol = MetasymbolLiteral () / OriginalSymbolExpr
// Expr
Expr = ExprWithoutBlock () / f
// Without Block
ExprWithoutBlock = LiteralExpr () / ExprWithoutBlock1
ExprWithoutBlock1 = StructExpr () / f
// Struct
StructExpr = StructExprStruct () / StructExpr1
StructExpr1 = StructExprTuple () / StructExprUnit
StructExprStruct = f f / f
StructExprTuple = PathInExpr StructExprTuple1 / f
StructExprTuple1 = '(' StructExprTuple2 / f
StructExprTuple2 = ZeroOrMoreExpr ')' / f
ZeroOrMoreExpr = Expr () / f
StructExprUnit = PathInExpr () / f
// PathInExpr
PathInExpr = ZeroOrOneDoubleColon OneOrMorePathExprSegment / f
ZeroOrOneDoubleColon = "::" () / ()
OneOrMorePathExprSegment = PathExprSegment () / f
PathExprSegment = PathIdentSegment PathExprSegment1 / f
PathExprSegment1 = "::" GenericArgs / ()
PathIdentSegment = Identifier () / f
GenericArgs = f f / f
// Literal
LiteralExpr = CharLiteral () / LiteralExpr1
LiteralExpr1 = StringLiteral () / LiteralExpr2
LiteralExpr2 = IntegerLiteral () / f
// Metasymbol
MetasymbolLiteral = EmptyLiteral () / MetasymbolLiteral1
MetasymbolLiteral1 = FailureLiteral () / MetasymbolLiteral2
MetasymbolLiteral2 = AnyLiteral () / MetasymbolLiteral3
MetasymbolLiteral3 = AllLiteral () / f
EmptyLiteral = "()" () / f
FailureLiteral = 'f' () / f
AnyLiteral = '?' ZeroOrMoreAny / f
ZeroOrMoreAny = '?' ZeroOrMoreAny / ()
AllLiteral = '*' () / f
// Original symbol
OriginalSymbolExpr = "{ " OriginalSymbolExpr1 / f
OriginalSymbolExpr1 = ExprWithoutBlock " }" / f
// Char
CharLiteral = '\'' CharLiteral1 / f
CharLiteral1 = InnerCharLiteral '\'' / f
InnerCharLiteral = NotCharLetter InnerCharLiteral1 / f
NotCharLetter = '\'' * / ()
InnerCharLiteral1 = QuoteEscape () / ?
// String
StringLiteral = '"' StringLiteral1 / f
StringLiteral1 = InnerStringLiteral '"' / f
InnerStringLiteral = InnerStringLiteralLetter InnerStringLiteral / ()
// InnerStringLiteralLetter
InnerStringLiteralLetter = NotStringLetter InnerStringLiteralLetter1 / f
NotStringLetter = '"' * / ()
InnerStringLiteralLetter1 = QuoteEscape () / ?
// Integer
IntegerLiteral = IntegerLiterals () / f
IntegerLiterals = DecLiteral () / f
DecLiteral = DecDigit ZeroOrMoreDecDigit / f
ZeroOrMoreDecDigit = DecDigitOrUnderscore ZeroOrMoreDecDigit / ()
DecDigitOrUnderscore = DecDigit () / '_'
// IDENTIFIER
Identifier = Uppercase ZeroOrMoreIdentifierContinue / f
ZeroOrMoreIdentifierContinue = IdentifierContinue ZeroOrMoreIdentifierContinue / ()
IdentifierContinue = Alphabet () / DecDigit
// Letters
Alphabet = Lowercase () / Uppercase
// Lowercase
LowercaseAToF = LowercaseAToF1 () / f
LowercaseAToF1 = 'a' () / LowercaseAToF2
LowercaseAToF2 = 'b' () / LowercaseAToF3
LowercaseAToF3 = 'c' () / LowercaseAToF4
LowercaseAToF4 = 'd' () / LowercaseAToF5
LowercaseAToF5 = 'e' () / LowercaseAToF6
LowercaseAToF6 = 'f' () / f
Lowercase = LowercaseAToF () / Lowercase1
Lowercase1 = 'g' () / Lowercase2
Lowercase2 = 'h' () / Lowercase3
Lowercase3 = 'i' () / Lowercase4
Lowercase4 = 'j' () / Lowercase5
Lowercase5 = 'k' () / Lowercase6
Lowercase6 = 'l' () / Lowercase7
Lowercase7 = 'm' () / Lowercase8
Lowercase8 = 'n' () / Lowercase9
Lowercase9 = 'o' () / Lowercase10
Lowercase10 = 'p' () / Lowercase11
Lowercase11 = 'q' () / Lowercase12
Lowercase12 = 'r' () / Lowercase13
Lowercase13 = 's' () / Lowercase14
Lowercase14 = 't' () / Lowercase15
Lowercase15 = 'u' () / Lowercase16
Lowercase16 = 'v' () / Lowercase17
Lowercase17 = 'w' () / Lowercase18
Lowercase18 = 'x' () / Lowercase19
Lowercase19 = 'y' () / Lowercase20
Lowercase20 = 'z' () / f
// Uppercase
UppercaseAToF = UppercaseAToF1 () / f
UppercaseAToF1 = 'A' () / UppercaseAToF2
UppercaseAToF2 = 'B' () / UppercaseAToF3
UppercaseAToF3 = 'C' () / UppercaseAToF4
UppercaseAToF4 = 'D' () / UppercaseAToF5
UppercaseAToF5 = 'E' () / UppercaseAToF6
UppercaseAToF6 = 'F' () / f
Uppercase = UppercaseAToF () / Uppercase1
Uppercase1 = 'G' () / Uppercase2
Uppercase2 = 'H' () / Uppercase3
Uppercase3 = 'I' () / Uppercase4
Uppercase4 = 'J' () / Uppercase5
Uppercase5 = 'K' () / Uppercase6
Uppercase6 = 'L' () / Uppercase7
Uppercase7 = 'M' () / Uppercase8
Uppercase8 = 'N' () / Uppercase9
Uppercase9 = 'O' () / Uppercase10
Uppercase10 = 'P' () / Uppercase11
Uppercase11 = 'Q' () / Uppercase12
Uppercase12 = 'R' () / Uppercase13
Uppercase13 = 'S' () / Uppercase14
Uppercase14 = 'T' () / Uppercase15
Uppercase15 = 'U' () / Uppercase16
Uppercase16 = 'V' () / Uppercase17
Uppercase17 = 'W' () / Uppercase18
Uppercase18 = 'X' () / Uppercase19
Uppercase19 = 'Y' () / Uppercase20
Uppercase20 = 'Z' () / f
QuoteEscape = "\\'" () / "\\\""
EndOfLine = "\r\n" () / '\n'
Space = ' ' () / f
// Digits
BinDigit = "0" () / "1"
OctDigit = BinDigit () / OctDigit1
OctDigit1 = "2" () / OctDigit2
OctDigit2 = "3" () / OctDigit3
OctDigit3 = "4" () / OctDigit4
OctDigit4 = "5" () / OctDigit5
OctDigit5 = "6" () / OctDigit6
OctDigit6 = "7" () / f
DecDigit = OctDigit () / DecDigit1
DecDigit1 = "8" () / DecDigit2
DecDigit2 = "9" () / f
// Comment
LineComment = "//" InnerLineComment / f
InnerLineComment = AnyExceptLF InnerLineComment / ()
AnyExceptLF = AnyExceptLF1 ? / f
AnyExceptLF1 = EndOfLine * / ()
TODO
Tasks
- into_first() in CST
- Add { Original } in mplg
- Add functions that easy to get Variable from AST
- Add RowColSpan
- Create parser from MPLG file.
- Error Handling
- Packrat Parsing
- Left Recursion
Next implementation
- Add functions that easy to get Variable from AST
- Can be Variable in Leaf Node
- Error Handling
Practice
Sequence
A <- e1 e2
A = e1 e2 / f
Choice
A <- e1 / e2
A = e1 () / e2
Zero or more
A <- e*
A = e A / ()
Not predicate
A <- !e ?
A = B ? / f
B = e * / ()
References
- Alexander Birman. The TMG Recognition Schema. PhD thesis, Princeton University, February 1970
- Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, N.J., 1972.
- Bryan Ford. 2002. Packrat parsing: a practical linear-time algorithm with backtracking. Ph.D. Dissertation. Massachusetts Institute of Technology.
- Bryan Ford. 2004. Parsing expression grammars: a recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 111–122.
- Hutchison, Luke AD. "Pika parsing: reformulating packrat parsing as a dynamic programming algorithm solves the left recursion and error recovery problems." arXiv preprint arXiv:2005.06444 (2020).
Dependencies
~1.5MB
~36K SLoC