DEV Community


Discussion on: Language Features: Best and Worst

validark profile image

A PEG is a parsing expression grammar. It is a way of specifying all valid strings in a language. It looks kinda like this

Statement <- FunctionCall
FunctionCall <- Identifier ( Arguments )
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Thread Thread
validark profile image

Bison and Yaac are tools that allow you to write a grammar and it will spit out a finite state machine like I described.

Forem Open with the Forem app