Кто о чём, а вшивый — о бане, в смысле, об очередной модели XML.
Если мы рассмотрим XML как цепочку символов StartTag a, EndTag a, Content a (или как говорят в соответствующей литературке — SAX), то совсем нетрудно будет заметить что он относится к классу языков сбалансированных скобок, т.е. не является регулярным.
Это не является проблемой самой по себе: мы всегда можем построить КА для разбора конкретной цепочки, и даже множества цепочек... Чем, собственно говоря, и занимаемся путём ваяния XML-схем различной степени упоротости.
А если есть способ? Нет понятно дело, можно перейти на новый уровень, взять МП-автомат и невозбранно юзать контекстно-свободные грамматики. Но тогда мы теряем всю алгебраическую вкусноту, присущую регулярным языкам... А в реальном мире алгебраические свойства регулярных языков куда важнее, чем возможность допускать более «широкие» множества цепочек!
Нет. Именно способ разбирать языки сбалансированных скобок, сохраяняя при этом все свойства регулярных языков. Как оказалось — есть!
Интуитивным объяснением почему КА не может разбирать языки сбалансированных скобок является отсутствие «памяти» . А если эту память можно присобачить?
Встречайте: Nested Word Automata (автоматы вложенных цепочек), а точнее его практическую реализацию Visibly Pushdown Automata.
Идея в том, что данный автомат жрёт три разных типа символов: «call» — обозначается как <a, «internal» — обозначается как a и «return» — обозначается как a>. Соответственно и функция переходов распадается на три: для символов «call» принимает текущее состояние и входящий call-сивол и возвращает следующее состояние и сивол который нужно засунуть на вершину стека, для «internal» принимает текущее состояние и входящий internal-символ и возвращает следующее состояние (т.е. как обычный КА), для «return» принимает текущее состояние, входящий internal-символ и символ с вершины стека и возвращает следующее состояние.
Т.е. в резултате мы получили класс МП-автомата, который не может за один символ запихивать и выпихивать символ из стека. Это повлияло на количество распознаваемых языков, но позволило сохранить свойства регулярных языков!
Более того, если у нас есть дерево t(a, b(c, d), e), то мы его можем закодировать как цепочку <t <a a> <b <c c> <d d> b> <e e> t>, т.е. ровно по такому же принципу как это делают SAX-парсеры.
За последний десякток лет была масса исследований на эту тему. С подборкой можно ознакомиться
madhu.cs.illinois.edu
cis.upenn.edu
Основополагающя статья Adding nesting structure to words: cis.upenn.edu
Слайды: cis.upenn.edu (с них лучше начать).
А теперь пара вопросов касательно первотега:
1. Неоднократно слышал что applicative-парсеры описывают регулярные языки. Где можно об этом почитать?
2. Кто-нибудь сталкивался с реализациями МП-автоматов на Х-е? Будут полезны также всякие LR/GLR/LALR реализации.
P.S.: Сабж применяется не только к XML, и вообще первоначально применялся для анализа программ, отсюда и call- и return- терминология.
Если мы рассмотрим XML как цепочку символов StartTag a, EndTag a, Content a (или как говорят в соответствующей литературке — SAX), то совсем нетрудно будет заметить что он относится к классу языков сбалансированных скобок, т.е. не является регулярным.
Это не является проблемой самой по себе: мы всегда можем построить КА для разбора конкретной цепочки, и даже множества цепочек... Чем, собственно говоря, и занимаемся путём ваяния XML-схем различной степени упоротости.
А если есть способ? Нет понятно дело, можно перейти на новый уровень, взять МП-автомат и невозбранно юзать контекстно-свободные грамматики. Но тогда мы теряем всю алгебраическую вкусноту, присущую регулярным языкам... А в реальном мире алгебраические свойства регулярных языков куда важнее, чем возможность допускать более «широкие» множества цепочек!
Нет. Именно способ разбирать языки сбалансированных скобок, сохраяняя при этом все свойства регулярных языков. Как оказалось — есть!
Интуитивным объяснением почему КА не может разбирать языки сбалансированных скобок является отсутствие «памяти» . А если эту память можно присобачить?
Встречайте: Nested Word Automata (автоматы вложенных цепочек), а точнее его практическую реализацию Visibly Pushdown Automata.
Идея в том, что данный автомат жрёт три разных типа символов: «call» — обозначается как <a, «internal» — обозначается как a и «return» — обозначается как a>. Соответственно и функция переходов распадается на три: для символов «call» принимает текущее состояние и входящий call-сивол и возвращает следующее состояние и сивол который нужно засунуть на вершину стека, для «internal» принимает текущее состояние и входящий internal-символ и возвращает следующее состояние (т.е. как обычный КА), для «return» принимает текущее состояние, входящий internal-символ и символ с вершины стека и возвращает следующее состояние.
Т.е. в резултате мы получили класс МП-автомата, который не может за один символ запихивать и выпихивать символ из стека. Это повлияло на количество распознаваемых языков, но позволило сохранить свойства регулярных языков!
Более того, если у нас есть дерево t(a, b(c, d), e), то мы его можем закодировать как цепочку <t <a a> <b <c c> <d d> b> <e e> t>, т.е. ровно по такому же принципу как это делают SAX-парсеры.
За последний десякток лет была масса исследований на эту тему. С подборкой можно ознакомиться
madhu.cs.illinois.edu
cis.upenn.edu
Основополагающя статья Adding nesting structure to words: cis.upenn.edu
Слайды: cis.upenn.edu (с них лучше начать).
А теперь пара вопросов касательно первотега:
1. Неоднократно слышал что applicative-парсеры описывают регулярные языки. Где можно об этом почитать?
2. Кто-нибудь сталкивался с реализациями МП-автоматов на Х-е? Будут полезны также всякие LR/GLR/LALR реализации.
P.S.: Сабж применяется не только к XML, и вообще первоначально применялся для анализа программ, отсюда и call- и return- терминология.