Když máme naleznena vypouštějící pravidla, můžeme hledat množiny terminálních symbolů, kterými začínají jednotlivá syntaktická pravidla.
Tyto množiny vyuzijeme při rozhodování, kterou alternativou má pokračovat parser.

http://gitlab.fjfi.cvut.cz/culikzde/view/-/blob/master/tutorial/plain-grammar/plain_symbols.py

Množiny budeme ukládat v jednotlivých třídách do proměnné first. Proměnná first bude pole,
indexem budou čísla označující terminální symboly,
hodnoty v poli budou True nebo False, podle toho zda terminální symbol patří do zmíněné množiny.

Na obrázku jsou čísla symbolů z našeho příkladu:

Pole first pro terminální symboly bude obsahovat jednu hodnotu True v místě odpovídajícím právě zpracovávanému terminálu.
tj. výsledkem bude jednoprvková množina

def firstFromTerminal (grammar, item) :
    # first set has one item
    item.first = newArray (grammar)
    inx = item.symbol_ref.inx
    item.first [inx] = True

Neterminální symboly získají množinu od svého pravidla.

Pokud navíc je pravidlo vypouštějící, má nastaveno nullable na True
“a může začínat ničím”, to se někdy označuje prázdným řetězcem, písmenem epsilon nebo v našem programu zápisem <empty>.

def firstFromNonterminal (grammar, item) :
    rule = item.rule_ref
    item.first = rule.first

Výrazy v závorkách mají stejnou množinu first jako výraz uvnitř závorek

def firstFromEbnf (grammar, ebnf) :
    firstFromExpression (grammar, ebnf.expr)
    # set ebnf according to expression
    ebnf.first = ebnf.expr.first

First pro jednu alternativu nejprve inicializujeme na prázdnou množinu.
Postupně přidáváme množiny pro jednotlivé gramatické prvky (provádíme sjednocení množin).
Pokud nalezneme nevypouštějící prvek, postup zastavíme.

Např. pokud alternativa začíná nevypouštějícím prvek, je výsledkem množina odpovídající tomuto prvku.
Pokud alternativa začíná vypouštějícím prvkem a za ním je nevypouštějící prvek je výsledkem sjednocení množin od obou prvků. <code Python> def firstFromAlternative (grammar, alt) : alt.first = newArray (grammar) for item in alt.items : if isinstance (item, Terminal) : firstFromTerminal (grammar, item) elif isinstance (item, Nonterminal) : firstFromNonterminal (grammar, item) elif isinstance (item, Ebnf) : firstFromEbnf (grammar, item) else : grammar.error (“Unknown alternative item: ” + item.class.name) # union for inx in range (grammar.symbol_cnt) : if item.first [inx] : alt.first [inx] = True # item is not nullable ⇒ stop adding symbols from items if not item.nullable : break </code> ==== Výrazy ==== Výsledkem bude sjednocení množin pro jednotlivé alternativy. Pokud množiny pro jednotlivé alternativy nejsou disjunktní,
nebude náš parser rozhodující se na základě jednoho právě čteného symbolu vědět jak má pokračovat. ( Rovněž vypouštějící altrenativy mohou védst k nejednoznačnostem. ) <code Python> def firstFromExpression (grammar, expr) : expr.first = newArray (grammar) for alt in expr.alternatives : firstFromAlternative (grammar, alt) # add symbols from alternative to expression for inx in range (grammar.symbol_cnt) : if alt.first [inx] : if expr.first [inx] : pass # grammar.error (“Conflict between alternatives”) expr.first [inx] = True </code> ==== Pravidla ==== Množiny first pro všechny pravidla nastavíme na prázdné množiny. Provedeme výpočet pro všechna pravidla.
Sledujeme, zda se změnila množina pro některé pravidlo.
Pokud se některá množina změnila, výpočty opakujeme. <code Python> def firstFromRules (grammar) : for rule in grammar.rules : rule.first = newArray (grammar) grammar.firstChanged = True while grammar.firstChanged : grammar.firstChanged = False for rule in grammar.rules : firstFromRule (grammar, rule) </code> <code Python> def firstFromRule (grammar, rule) : expr = rule.expr firstFromExpression (grammar, expr) equal = True for inx in range (grammar.symbol_cnt) : if rule.first [inx] != expr.first [inx] : equal = False if not equal : rule.first = expr.first grammar.firstChanged = True </code> Pomocné funkce pro vytvoření prázdné množiny a kopírování množin. <code Python> def newArray (grammar) : return [False] * grammar.symbol_cnt def copyArray (grammar, source) : result = newArray (grammar) for inx in range (grammar.symbol_cnt) : if source [inx] : result [inx] = True return result </code> ====== Zobrazení množiny symbolů ====== http://gitlab.fjfi.cvut.cz/culikzde/simple-view/-/blob/master/tutorial/plain-grammar/plain_view.py Modře jsou zobrazeny množiny symbolů.
Zeleně pravidla, která mají množiny s dvěma a více prvky.