Algoritmo de análise multinível

Question

reformular ...

Eu gostaria de saber como melhor analisar funções/condicionais. Então, se você tem algo como: [if {a} is {12 or 34}][if {b} not {55}] show +c+ [/if][/if] que é um condicional dentro de um condicional. Parece que não posso fazer isso apenas com Regex.

---

pergunta original

Por enquanto, tenho uma maneira bastante simples de analisar alguns comandos através do ActionScript.

Estou usando o regexp para encontrar tags, comandos e operações usando ...

+key_word+  // any text surrounded by +
[ifempty +val_1+]+val_2+[/ifempty]  //simple conditional
[ifisnot={`true,yes`} +ShowTitle+]+val_3+[/ifisnot]  // conditional with operands

Meu algoritmo atual corresponde à etiqueta de abertura[**] com a primeira tag de fechamento [/**] Mesmo que não corresponda. O que significa que eu não poderia fazer algo como [ifempty +val_2+][ifnotempty +val_2]+val_3+[/ifnotempty]+val_4+[/ifempty] - colocando essencialmente um condicional dentro de outro.

Estou usando uma maneira embutida de análise que divide a corda em uma matriz de strings com base neste regexp \[[^\/](?:[^\]])*\](?:[^\]])*\[\/(?:[^\]])*\]

Alguém pode sugerir um algoritmo mais robusto com uma convenção/padrão de análise mais robusta? especialmente para AS3.

Answer 1

Expressões regulares definem idiomas regulares. Idiomas regulares não podem ter regiões de recursão restrita, mas potencialmente infinita.

Uma maneira de pensar sobre isso é que todos os idiomas regulares podem ser representados por uma máquina de estado finita. Você precisaria de um estado para cada número possível de IF, mas a máquina deve ser 'finita', então você está em um encadernador. Um exemplo clássico é:

a{n}b{n}, n >= 0
(meaning n a's, followed by n b's)

Ao analisar cada A, você precisaria ir para outro estado (os FSMs não têm memória além do estado, essa é a única maneira de se lembrar de N para combiná -lo mais tarde). Para analisar qualquer número de N, você precisaria de um número infinito de estados.

Essa é a mesma situação em que você está, uma expressão regular pode expressar um número finito de IFS (embora seja necessário um pouco de cópia), mas não um número infinito. Observe, no entanto, que algumas implementações regulares de expressão traem um pouco, dando -lhes mais poder do que seus equivalentes matemáticos.

De qualquer forma, sua melhor aposta é usar um método de análise mais poderoso. UMA Analisador de descida recursiva é particularmente divertido de implementar e pode facilmente fazer o que você precisa. Você também pode procurar um LR-Parser ou construir um analisador simples usando uma pilha. Dependendo do seu idioma, você poderá encontrar uma biblioteca de análise, como Pyparse, para Python ou Boost Spirit para C ++.