daniel-boll / pile Goto Github PK
View Code? Open in Web Editor NEWThe oficial repo for the pile lang
The oficial repo for the pile lang
A code able to parse any grammar that respects the following specification:
LHS -> RHS
Production
entityProduction
Terminal
Empty
|
<S> -> <S> s | s
Should create something along the lines of
GrammarContent{{
{Production{"S"}, {Production{"S"}, Terminal{"s"}}},
{Production{"S"}, {Terminal{"s"}}},
}}
And
<S> -> <S> s | s | <S> <B> ε
GrammarContent{{
{Production{"S"}, {Production{"S"}, Terminal{"s"}}},
{Production{"S"}, {Terminal{"s"}}},
{Production{"S"}, {Production{"S"}, Production{"B"}, Empty{}}},
}}
Must notice that ε
creates an Empty{}
entity and not a Terminal{"ε"}
The LL(1) parser will receive a LL(1) grammar expecting it to be already LL(1) compliant. The purpose of this top-down analysis is to create a AST (Abstract Syntax Tree) deriving left-to-right.
We have to establish what grammar rule the parser should choose if it sees a nonterminal
The first set represents the possible characters found from that nonterminal
Given a grammar with the rules
Unfortunately, the First-sets are not sufficient to compute the parsing table. This is because a right-hand side
Computing the Follow-sets for the nonterminals in a grammar can be done as follows:
It is a bidimensional matrix in the format
$M[\Delta, \alpha]$ where$\Delta$ is a nonterminal and$\alpha$ is a terminal.
Now we can define exactly which rules will appear where in the parsing table. If
Equivalently:
If the table contains at most one rule in every one of its cells, then the parser will always know which rule it has to use and can therefore parse strings without backtracking. It is in precisely this case that the grammar is called an LL(1) grammar.
Items
<A> -> <C> <D> <E>
<A> -> · <C> <D> <E>
<A> -> <C> · <D> <E>
<A> -> <C> <D> · <E>
<A> -> <C> <D> <E> ·
(reduction)<A> -> ε
=> <A> -> ·
<S'>
to the grammar.<S'> -> <S>
to the grammar that indicates to the analyzer when to stop.Considering I
as the set of LR items, the closure of I
is the set of LR items that can be reached from I
by applying the following rules:
I
is added to the closure of I
A -> α · B β
is in I
and B -> γ
is a production in the grammar, then B -> · γ
is added to the closure of I
Given the grammar:
<E'> -> <E>
<E> -> <E> + <T> | <T>
<T> -> <T> * <F> | <F>
<F> -> ( <E> ) | id
If I
is the set of the item {[<E'> -> · <E>]}
then:
closure(I) = {
<E'> -> · <E>
<E> -> · <E> + <T>
<E> -> · <T> // brings all of T
<T> -> · <T> * <F>
<T> -> · <F> // brings all of F
<F> -> · ( <E> )
<F> -> · id
}
The operatio Goto(I, X) returns the closure of the set of LR items that can be reached from I
by shifting the dot over the symbol X
.
I
where the symbol after the dot is X
.
<A> -> <α> · <X> <β>
in I
and <x> = X
add <A> -> <α> <X> · <β>
to the closure of I
<S'> -> <T>
<T> -> <F> | <T> * <F>
<F> -> id | ( <T> )
closure(I) = {
<S'> -> · <T>
<T> -> · <F>
<T> -> · <T> * <F>
<F> -> · id
<F> -> · ( <T> )
}
shift(I, () = {
<F> -> ( · <T> )
<T> -> · <F>
<T> -> · <T> * <F>
<F> -> · id
<F> -> · ( <T> )
}
shift(I, id) = {
<F> -> id ·
}
shift(I, <F>) = {
<T> -> <F> ·
}
shift(I, <T>) = {
<S'> -> <T> ·
<T> -> <T> · * <F>
}
The SLR(1) parsing table is a table that contains the actions that the parser should take for each state and each symbol. It consists in calculate
the sets parting from the initial state and then calculate the goto for each symbol of the grammar.
The I_0
is the initial state and the I_n
is the final state. I_0=[S' -> · <S>]
Pseudo
// @input: extended grammar G'
// @output: SLR syntatic actions and gotos for G'
function table(G') {
1. Build C={I_0..I_n}
2. The ith state is built from I_i. The syntatic actions for the state i are determined by:
2.1 If [A -> α · a β] is in I_i and a is a terminal, then shift[I_i, a] = shift j, where j is the state that contains [A -> α a · β].
2.2 If [A -> α ·] is in I_i, then reduce[A -> α] = reduce A for every `α` in Follow(A).
2.3 If [S' -> S ·] is in I_i, then accept = accept.
3. The syntatic gotos for the state i are determined by:
3.1 If shift[I_i, a] = shift j, then shift[i, a] = j.
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.