inferendo programmaticamente terminali e non-terminali in grammatiche context-free?

Question

inferendo programmaticamente terminali e non-terminali in grammatiche context-free?

#1 da (2 voti)

2

Sto provando a calcolare i set FIRST e FOLLOW di un CFG (usando Python).

Per fare questo ho bisogno di riconoscere terminali e non-terminali. Posso (come umano) leggerli, ma mi chiedevo se esistesse una logica computazionale per inferire terminali e non-terminali, se si è data solo la grammatica.

Sembra che sia necessario costruire l'albero di analisi e quindi etichettare terminali e non-terminali? Un terminale è un nodo che non ha figli.

Si potrebbe anche usare la definizione di "terminali" e "non-terminali":

Terminals

A terminal is a symbol which does not appear on the left-hand side of any production.

Nonterminals

Nonterminals are the non-leaf nodes in a parse tree.

O forse i non-terminali sono anche tutti quelli che non rientrano nella definizione di terminali.

link

grammar

posta mavavilj 31.12.2015 - 22:53

fonte

1 risposta

Leggi altre domande sui tag grammar

Concetto per distinguere tra tag HTML e parentesi angolari Utilizzo di bean prototype / non-Spring nell'applicazione Spring Web

score 2 · Accepted Answer

Questo dovrebbe essere abbastanza semplice. Supponendo una grammatica come:

expr:   ID | STR | NUM | list
list:   ( seq )  
seq:       | expr seq

Puoi raccogliere i simboli in ogni produzione (ID, STR, NUM, elenco, (, seq,), expr e niente ) e quindi estrarre i simboli di produzione stessi (expr, elenco , seq). Questo ti dà due set, i terminali e i non-terminali (e niente , che potresti volere o meno a seconda delle tue esigenze).