Разница между хомским типом 3 и грамматикой типа Хомски 2

У меня возникают проблемы с выражением разницы между типом 2-го Хомского (контекстно-свободные языки) и хомским типом 3 (обычные языки).

Может ли кто-нибудь дать мне ответ на простом английском языке? Мне трудно понять всю иерархию.

Ответ 1

Типа II - грамматика типа III со стеком

Грамматика типа II в основном представляет собой грамматику типа III с вложением.

Грамматика типа III (Regular):

Use Case - CSV (значения, разделенные запятыми)

Технические характеристики:

может быть прочитан с использованием FSM (конечный автомат)
не требует промежуточного хранения
можно читать с помощью регулярных выражений
обычно выражается с использованием структуры данных 1D или 2D.
является плоским, что означает отсутствие свойств вложенности или рекурсии.

Пример:

this,is,,"an "" example",\r\n
"of, a",type,"III\n",grammar\r\n

Пока вы можете определить все правила и крайние случаи для вышеуказанного текста, вы можете проанализировать CSV.

Грамматика типа II (без контекста):

Use Case - HTML (язык разметки гипертекста) или SGML вообще

Технические характеристики:

можно прочитать с помощью DPDA (автоматы детерминированной точечной печати)
потребуется стек для промежуточного хранилища
может быть выражен как 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 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-код, который был бы определен, был бы рассмотрен как тип я (Ie Context Sensitive). Причина в том, что когда парсер достигает плохо структурированного кода, он фактически принимает решения о том, как интерпретировать код на основе окружающего контекста. Например, если в элементе отсутствуют его закрывающие теги, ему необходимо определить, где этот элемент существует в иерархии, прежде чем он сможет решить, где должен быть размещен закрывающий тег.

Другие функции, которые могут сделать контекстно-зависимый язык контекстно-зависимыми, включают в себя шаблоны, импорт, препроцессоры, макросы и т.д.

Короче говоря, контекстно-зависимые языки очень похожи на языки, не содержащие контекста, но элементы контекстно-зависимых языков могут интерпретироваться по-разному в зависимости от состояния программы.

Отказ от ответственности: я официально не обучаюсь в CompSci, поэтому этот ответ может содержать ошибки или предположения. Если вы спросите меня о разнице между терминалом и не-терминалом, вы заработаете себе пустой взгляд. Я многому научился, фактически создав синтаксический анализатор типа III (обычный) и внимательно прочитав об остальных.

Ответ 2

На странице wikipedia есть хорошие снимки и маркеры.

Грубо говоря, базовая машина, которая может описывать обычный язык, не нуждается в памяти. Он запускается как statemachine (DFA/NFA) на входе. Регулярные языки также могут быть выражены с помощью регулярных выражений.

Язык с добавленным к нему "следующим" уровнем сложности - это свободный от контекста язык. Базовая машина, описывающая этот тип языка, нуждается в некоторой памяти, чтобы иметь возможность представлять языки, которые являются свободными от контекста и не являются регулярными. Обратите внимание, что добавление памяти на ваш компьютер делает ее немного более мощной, поэтому она все равно может выражать языки (например, обычные языки), для которых не требуется память. Основной машиной обычно является push-down automaton.

Ответ 3

Тип 3 грамматики состоит из ряда состояний. Они не могут выразить вложение. Например, грамматика типа 3 не может требовать сопоставления скобок, поскольку она не может показать, что скобки должны быть "обернуты" их содержимым. Это связано с тем, что, как указывает Дерек, грамматика типа 3 не "запоминает" что-либо о предыдущих состояниях, которые она прошла, чтобы перейти в текущее состояние.

Тип 2 грамматики состоит из набора "постановок" (вы можете думать о них как о шаблонах), которые могут иметь встроенные в них другие произведения. Таким образом, они рекурсивно определены. Производство может быть определено только с точки зрения того, что он содержит, и не может "видеть" вне себя; это то, что делает грамматику без контекста.