Разница между хомским типом 3 и хомским типом 2 грамматики
У меня возникли проблемы с формулированием различий между Chomsky type 2 (контекстно-свободные языки) и Chomsky type 3 (Regular Languages).
Может ли кто-нибудь дать мне ответ на простом английском? У меня проблемы с пониманием всей иерархии.
3 ответа
Грамматика типа II - это грамматика типа III со стеком
Грамматика типа II - это в основном грамматика типа III с вложенностью.
Тип III грамматика (обычная):
Вариант использования - CSV (значения, разделенные запятыми)
Характеристики:
- можно прочитать с помощью FSM (конечного автомата)
- не требует промежуточного хранения
- можно читать с помощью регулярных выражений
- обычно выражается с использованием 1D или 2D структуры данных
- плоский, что означает отсутствие вложенности или рекурсивные свойства
Пример:
this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n
Пока вы можете выяснить все правила и крайние случаи для приведенного выше текста, вы можете анализировать CSV.
Тип II грамматики (без контекста):
Вариант использования - HTML (язык гипертекстовой разметки) или SGML в целом
Характеристики:
- может быть прочитан с использованием DPDA (детерминированных автоматов Pushdown)
- потребуется стек для промежуточного хранения
- может быть выражено как AST (абстрактное синтаксическое дерево)
- может содержать вложенные и / или рекурсивные свойства
HTML может быть выражен как обычная грамматика:
<h1>Useless Example</h1>
<p>Some stuff written here</p>
<p>Isn't this fun</p>
Но попробуйте разобрать это с помощью FSM:
<body>
<div id=titlebar>
<h1>XHTML 1.0</h1>
<h2>W3C's failed attempt to enforce HTML as a context-free language</h2>
</div>
<p>Back when the web was still pretty boring, the W3C attempted to standardize away the quirkiness of HTML by introducing a strict specification</p
<p>Unfortunately, everybody ignored it.</p>
</body>
Увидеть разницу? Представьте, что вы пишете парсер, вы можете начать с открытого тега и закончить с закрывающим тегом, но что произойдет, если вы встретите второй открывающий тег, прежде чем достигнете закрывающего тега?
Все просто, вы помещаете первый открывающий тег в стек и начинаете анализировать второй тег. Повторите этот процесс для всех существующих уровней вложенности, и если синтаксис хорошо структурирован, стек можно развернуть по одному слою за раз на противоположном уровне, который был построен
Из-за строгой природы "чистых" контекстно-свободных языков они относительно редки, если они не генерируются программой. JSON, это яркий пример.
Преимущество контекстно-свободных языков заключается в том, что, хотя они очень выразительны, их все же относительно просто анализировать.
Но подождите, разве я не сказал, что HTML не зависит от контекста. Да, если он хорошо сформирован (то есть XHTML).
В то время как XHTML может считаться не зависящим от контекста, более слабый HTML-код на самом деле считался бы Типом I (т.е. чувствительным к контексту). Причина в том, что когда синтаксический анализатор достигает плохо структурированного кода, он фактически принимает решение о том, как интерпретировать код на основе окружающего контекста. Например, если элементу не хватает своих закрывающих тегов, ему необходимо определить, где этот элемент существует в иерархии, прежде чем он сможет решить, где должен быть размещен закрывающий тег.
Другие функции, которые могут сделать контекстно-зависимый язык контекстно-зависимым, включают шаблоны, импорт, препроцессоры, макросы и т. Д.
Короче говоря, контекстно-зависимые языки очень похожи на контекстно-зависимые языки, но элементы контекстно-зависимых языков могут интерпретироваться по-разному в зависимости от состояния программы.
Отказ от ответственности: я официально не обучен CompSci, поэтому этот ответ может содержать ошибки или предположения. Если вы спросите меня разницу между терминалом и нетерминалом, вы заработаете себе пустой взгляд. Я многому научился, фактически создав парсер типа III (Regular) и много читая об остальном.
Страница Википедии имеет хорошую картинку и точечные обозначения.
Грубо говоря, базовая машина, которая может описывать обычный язык, не нуждается в памяти. Он работает как машина состояний (DFA/NFA) на входе. Регулярные языки также могут быть выражены с помощью регулярных выражений.
Язык, к которому добавлен "следующий" уровень сложности, является языком без контекста. Базовой машине, описывающей этот тип языка, потребуется некоторая память, чтобы иметь возможность представлять языки, которые не зависят от контекста и не являются регулярными. Обратите внимание, что добавление памяти на ваш компьютер делает его немного более мощным, поэтому он может по-прежнему выражать языки (например, обычные языки), которым для начала не требовалась память. Базовая машина - это, как правило, автомат с нажатием.
Грамматика типа 3 состоит из ряда состояний. Они не могут выразить вложение. Например, грамматика типа 3 не может требовать совпадения скобок, поскольку она не может показать, что скобки должны быть "обернуты" вокруг их содержимого. Это потому, что, как указывает Дерек, грамматика типа 3 "ничего не помнит" о предыдущих состояниях, через которые она прошла, чтобы добраться до текущего состояния.
Грамматики типа 2 состоят из набора "произведений" (вы можете думать о них как о шаблонах), в которые могут быть встроены другие произведения. Таким образом, они определены рекурсивно. Производство может быть определено только в терминах того, что оно содержит, и не может "видеть" вне себя; это то, что делает грамматику контекстно-свободной.