Che tipo di parser è necessario per questa grammatica?

Question

Ho una grammatica che non conosco quale tipo di parser ho bisogno per analizzarlo a parte non credo che la grammatica sia LL (1). Sto pensando che ho bisogno di un parser con backtracking o LL (*) di qualche tipo. La grammatica che ho si avvicinò con (che potrebbe essere necessaria una riscrittura) è:

S: Rules 
Rules: Rule | Rule Rules 
Rule: id '=' Ids 
Ids: id | Ids id 

Il linguaggio che sto cercando di generare sembra qualcosa di simile:

abc = def g hi jk lm 
xy = aaa bbb ccc ddd eee fff jjj kkk 
foo = bar ha ha 

Zero o più regola che contiene la sinistra identificatore seguito da un segno di uguale seguito da uno o più identificatori. La parte che penso avrò un problema nella scrittura di un parser è che la grammatica consente qualsiasi quantità di id in una regola e che l'unico modo per dire quando inizia una nuova regola è quando trova id =, che richiederebbe il backtracking.

Qualcuno conosce la classificazione di questa grammatica e il miglior metodo di analisi, per un parser scritto scritto da?

Answer 1

La grammatica che genera un identificativo seguito da un segno di uguale seguito da una sequenza finita di identificatori è regolare. Ciò significa che le stringhe nella lingua possono essere analizzate utilizzando un DFA o un'espressione regolare. Non c'è bisogno di fantasia non deterministica o LL (*) parser.

di vedere che il linguaggio è regolare, diamo Id = U {un: un ∈ Γ}, dove Γ ⊂ Σ è l'insieme di simboli che possono verificarsi negli identificatori. La lingua che si sta tentando di generare è indicato con l'espressione regolare

• Id⁺ = (Id⁺) ^*Id⁺

Impostazione Γ = {a, b, ..., z}, esempi di stringhe nel linguaggio dell'espressione regolare sono:

• sguardo = io sono in un linguaggio regolare
• hey = Questo significa che possono essere riconosciuti da un dfa
• fresco = o anche un'espressione regolare

non v'è alcuna necessità di analizzare la lingua utilizzando potenti tecniche di analisi. Questo è un caso in cui l'analisi mediante espressioni regolari o DFA è sia appropriata che ottimale.

edit:

chiamata sopra espressione regolare R.Per analizzare R^*, generare un DFA riconoscendo la lingua di R^*. Per fare ciò, generare un NFA riconoscendo la lingua di R^* utilizzando l'algoritmo ottenibile dal teorema di Kleene. Quindi convertire l'NFA in un DFA usando la costruzione del sottoinsieme. Il DFA risultante riconoscerà tutte le stringhe in R^*. Data una rappresentazione del DFAE costruito nel vostro linguaggio di implementazione, le azioni necessarie - per esempio,

• Aggiungere l'ultimo identificatore analizzato per il lato destro della istruzione di dichiarazione corrente che viene analizzato
• Aggiungere l'ultima dichiarazione istruzione analizzata in un elenco di dichiarazioni analizzate e utilizzare l'ultimo identificativo analizzato per iniziare l'analisi di una nuova dichiarazione

può essere codificato negli stati di DFA. In realtà, l'uso del teorema di Kleene e la costruzione di sottoinsiemi non è probabilmente necessario per un linguaggio così semplice. Cioè, probabilmente puoi semplicemente scrivere un parser con le due azioni precedenti senza implementare un automa. Data una langauge regolare più complicata (ad esempio, la struttura lessicale di una langauge di programmazione), la conversione sarebbe l'opzione migliore.