These would be converted into a Finite State Automata that can parse a string in LL(1) or O(n). It's basically a program that takes one character after another and changes state depending on the character. Each state can accept different characters leading to different states. This way, a state can encompass multiple non-terminals.
Let's say you define a language as having members "hero" and "hello".
MyLang <- hello | hero
The way to parse a given string without backtracking or lookahead is to construct this finite state machine. Opening state accepts an h, leading to state 1. State 1 accepts e, leading to state 2. State 2 accepts l, leading to state 3, or r leading to state 4. State 3 accepts l, leading to state 5, which accepts o, leading to a state which it is valid to end on. State 4 also accepts an o and is valid to end on. In this case you could reuse state 4 for 5 if desired.
A PEG is a parsing expression grammar. It is a way of specifying all valid strings in a language. It looks kinda like this
These would be converted into a Finite State Automata that can parse a string in LL(1) or O(n). It's basically a program that takes one character after another and changes state depending on the character. Each state can accept different characters leading to different states. This way, a state can encompass multiple non-terminals.
Let's say you define a language as having members "hero" and "hello".
The way to parse a given string without backtracking or lookahead is to construct this finite state machine. Opening state accepts an
h, leading to state 1. State 1 acceptse, leading to state 2. State 2 acceptsl, leading to state 3, orrleading to state 4. State 3 acceptsl, leading to state 5, which acceptso, leading to a state which it is valid to end on. State 4 also accepts anoand is valid to end on. In this case you could reuse state 4 for 5 if desired.Bison and Yaac are tools that allow you to write a grammar and it will spit out a finite state machine like I described.