Должен ли я использовать генераторы синтаксических анализаторов для чего-либо еще, кроме языка?

Пытаясь освоиться с лексическими анализаторами и генераторами парсеров, я понял, что большинство ресурсов в Интернете (учебники, форумы, StackOverflow) говорят только о языках. Это потому, что такие инструменты, как Flex и Bison, подходят только для языков, или потому что все, что можно проанализировать, считается языком?

Чтобы быть более конкретным, у меня есть файл следующего вида:

File    : Bananarama.xyz
Date    : 22.12.2017

TableStart
BlockStart
Param1       : 12
Param2       : 1.5
Param3[lbs]  : 1539
Param4[cm]   : 55
BlockEnd

BlockStart
[...]
BlockEnd
TableEnd

Подходит ли этот файл для анализа с помощью LALR-Parser?


parsing flex-lexer bison lalr
person exilit    schedule 13.01.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

(Письменные) Языки — это не что иное, как структурированные последовательности символов, которые содержат информацию. Это ничем не отличается от того, что у вас есть. Файлы данных, файлы настроек конфигурации — все это последовательности символов, которые содержат информацию. Порядок и последовательность символов необходимо распознать, чтобы обнаружить (или сопоставить) содержащуюся в них информацию.

Однако существуют различные способы структурирования символов для представления информации. Некоторые способы организации символов распознать легче, чем другие. Под проще я подразумеваю меньше кода, меньше времени и более простые алгоритмы. Некоторые сложнее.

То, что вы спрашиваете, на самом деле означает: «Требуется ли для распознавания этого примерного расположения символов алгоритм такой сложности?»

Ответ прост: информатика. Я бы просто использовал иерархию Хомского, чтобы оценить тип алгоритма, необходимого для синтаксического анализа (сопоставления) последовательности символов в файле.

Без дальнейших подробных объяснений достаточно сказать, что язык относится либо к типу 2, либо к типу 3 и, безусловно, может быть проанализирован LALR-парсером. Осталось решить только один вопрос: не слишком ли сложен LALR-парсер для этого языка.

Можем ли мы использовать обычную грамматику (и, следовательно, регулярные выражения) для этой задачи? Вашего примера файловой структуры на самом деле недостаточно для ответа на этот вопрос. Вам нужно знать, могут ли структуры быть вложенными или нет. Может ли BLOCK содержать BLOCK или нет?

Если нет вложенности, регулярные выражения достаточно мощны, и есть множество инструментов, которые выполняют эту работу (например, egrep, perl, awk, sed, findstr).

person Brian Tompsett - 汤莱恩    schedule 13.01.2017
comment
Что ж, блок не может содержать другой блок, но я немного упростил пример. Все блоки окружены парой TableStart/TableEnd (я отредактировал вопрос). Но это ничего не меняет, не так ли? - person exilit; 13.01.2017
comment
Другой вопрос: не вводят ли Блоки какую-то контекстную чувствительность, чтобы он стал языком типа 1? - person exilit; 13.01.2017
comment
@exilit Контекстно-зависим только в том случае, если символы в одном блоке изменяют синтаксис следующих блоков, то есть грамматика изменяется по мере сопоставления символов. Судя по вашему примеру, это не так. Возможно, вы путаете синтаксис с семантикой данных. - person Brian Tompsett - 汤莱恩; 13.01.2017
comment
Да, я думаю, что вы правы, я, скорее всего, путаю, так как я совершенно неопытен в разборе. - person exilit; 13.01.2017
comment
Спасибо за ссылку. Я посмотрю на это. - person exilit; 13.01.2017