L'algoritmo dello shunting può analizzare le espressioni regolari POSIX?

Question

A prima vista, il shunting yard algorithm sembra applicabile all'analisi delle espressioni regolari POSIX, ma poiché non ho molta esperienza (o background teorico) nella scrittura dei parser, vorrei chiedere SO prima di saltare e scrivere qualcosa solo per ottenere bloccato a metà strada.

Forse una versione più sofisticata della domanda è: qual è una buona affermazione formale della classe di problemi a cui può essere applicato l'algoritmo dello shunting yard?

Chiarimento: Questa domanda è se è possibile analizzare POSIX ri sintassi in un albero di sintassi astratta utilizzando i principi di base dell'algoritmo di manovra, non è se è possibile utilizzare le espressioni regolari per implementare l'algoritmo di smistamento. Mi spiace di non essere stato abbastanza chiaro affermando che per cominciare!

Answer 1

Dirò che la risposta alla tua domanda è "no, non è possibile implementare l'algoritmo dello shunting utilizzando un'espressione regolare". Questo è per lo stesso motivo per cui non è possibile analizzare codice HTML arbitrario utilizzando espressioni regolari. Il che si riduce a questo:

Le espressioni regolari non hanno uno stack. Poiché l'algoritmo dello shunting yard si basa su uno stack (per eseguire il push e il pop degli operandi durante la conversione da infisso a RPN), le espressioni regolari non hanno il "potere" computazionale per eseguire questa attività.

Questo glossa molti dettagli, ma una "espressione regolare" è un modo per definire un linguaggio normale. Quando "usi" un'espressione regolare, chiedi al computer di dire: "Guarda un corpo di testo e dimmi se alcune di queste stringhe sono nella mia lingua, la lingua che ho definito usando un'espressione regolare". Indirizzerò a this most excellent answer which you and everyone reading this should upvote per ulteriori informazioni sulle lingue regolari.

Quindi ora è necessario un concetto matematico per aumentare "lingue regolari" al fine di creare linguaggi più potenti. Se dovessimo caratterizzare l'algoritmo dello shunting yard come una realizzazione di un modello di potenza computazionale, potreste dire che l'algoritmo sarebbe descritto come context-free grammar (ehi, sapete, quel link usa un albero di analisi delle espressioni come esempio.) A push-down automata. Qualcosa con una pila.

Se non hai familiarità con la teoria degli automi e le classi di complessità, allora quegli articoli di Wikipedia non sono probabilmente così utili senza spiegarli da zero.

Il punto è che si può essere in grado di utilizzare regex per aiutare a scrivere lo scalo di smistamento. Ma le regex non sono molto buone nel fare operazioni che hanno una profondità arbitraria, che questo problema ha. Quindi non passerei troppo tempo a percorrere il viale regex per questo problema.

Answer 2

Non vedo perché non sarebbe adatto. Guardando un vecchio codice, sembra che ho usato una strategia di parsing completamente diversa per il mio parser regexp, tuttavia (essenzialmente, un walk-through dall'inizio, costruendo la rappresentazione dell'automa risultante mentre si va, con qualche look-ahead e ricorsivo chiama per implementare il raggruppamento di espressioni regolari).

Answer 3

Sono abbastanza sicuro che sia possibile. Se si guarda al normale pacchetto di espressione di Henry Spencer:

regexp.shar.Z

che era alla base per le espressioni regolari del Perl, si noterà che egli descrive il programma come in "ferrovia forma normale".

Answer 4

Suppongo che avresti qualche problema perché caratteri diversi hanno significati diversi in contesti diversi, ad es.

^[^a-z][asd-] 

Il ^ ha due significati diversi e così fa il -. Penso che sceglierei un parser di discesa ricorsivo.