Ответ 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 (обычный) и внимательно прочитав об остальных.