многоуровневый алгоритм синтаксического анализа

Question

Перефразировать ...

Я хотел бы знать, как лучше разобрать функции/условными. поэтому, если у вас есть что-то вроде: [if {a} is {12 or 34}][if {b} not {55}] show +c+ [/if][/if], который является условным внутри условного. Похоже, я не могу делать это только с регулярным выражением.

---

оригинального вопрос

сейчас у меня есть довольно простой способ разбора некоторых команд через ActionScript.

Я использую регулярное выражение для поиска меток, команды и операндов, используя ...

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

моего текущего алгоритм соответствует открывающему тегу [**] с первым закрывающим тегом [/**], даже если он не соответствует. Это означает, что я не мог сделать что-то вроде [ifempty +val_2+][ifnotempty +val_2]+val_3+[/ifnotempty]+val_4+[/ifempty] - по существу, один условный внутри другого.

Я использую встроенный способ синтаксического анализа, который делит строку на массив строк на основе этого регулярного выражения \[[^\/](?:[^\]])*\](?:[^\]])*\[\/(?:[^\]])*\]

кто может предложить более надежный алгоритм с более надежной разборе конвенции/стандартом? особенно для as3.

Answer 1

Регулярные выражения определяют обычные языки. У обычных языков не может быть регионов с ограниченной, но потенциально бесконечной рекурсией.

Один из способов задуматься о том, что все обычные языки могут быть представлены машиной конечного состояния. Вам понадобится состояние для каждого возможного числа if, но машина должна быть «конечной», поэтому ваша в привязке. Классический пример является:

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

Как разобрать каждый а, вам нужно будет перейти в другое состояние (конечные автоматы не имеют памяти за пределами государства их в, что это единственный способ, которым они могли бы вспомнить п, чтобы соответствовать его позже) , Чтобы разобрать любое число n, вам понадобится бесконечное количество состояний.

Это та же самая ситуация, в которой вы находитесь, регулярное выражение может выражать конечное число ifs (хотя это займет совсем немного копирования), но не бесконечное число. Обратите внимание, однако, что некоторые реализации регулярных выражений немного обманывают, давая им больше энергии, чем их математические эквиваленты.

В любом случае, лучше всего использовать более мощный метод синтаксического анализа. A recursive descent parser особенно интересен для реализации и может легко делать то, что вам нужно. Вы также можете заглянуть в LR-парсер или создать простой парсер, используя стек. В зависимости от вашего языка вы можете найти библиотеку синтаксического анализа, такую ​​как pyparse для Python или Boost Spirit для C++.