Определение языка

Исследование алгоритмов требует анализа языков. Анализ языка начинается с описания грамматики. Язык Spp используется для описания грамматики.

Установка Spp (на примере Go)

Для Spp существует Yöntemleri 5 реализации на различных языках программирования. Выберите ту, которая вам наиболее знакома (Go — самая быстрая):

https://gitee.com/str/go-spp
https://gitee.com/str/lua-spp
https://gitee.com/str/ruby-spp
https://gitee.com/str/perl-spp
https://gitee.com/str/python-spp

Сначала убедитесь, что ваш компьютер имеет установленную среду выполнения Go или другого выбранного вами языка программирования. В директории git находится файл Spp.go, который следует скачать. В командной строке выполните следующую команду:

> go run Spp.go

Это Spp REPL, нажмите Enter для выхода.              
>>

Теперь вы можете начать обучение и тестирование.

Базовая синтаксическая конструкция Spp

Строка: есть два способа представления

>> Str -> 'abc'
["Str","'abc'"]

Как видно, это похоже на JSON, но это его подмножество, без объектов, true, false...

>> Str -> "abc"
["String","\"abc\""]

>> Str -> :abc
["Kstr",":abc"]

Строки могут быть представлены тремя способами, чтобы сделать работу более удобной.

В одинарных кавычках строки не должны содержать одинарных кавычек; если они присутствуют, то они должны быть экранированы.

>> str -> 'abc\'\\'
["Str","'abc\\'\\\\'"]

Аналогично, двойные кавычки также не должны содержать двойных кавычек.

Символ: представляет невидимый символ

Char -> ' ["Char","\'"]

Любое символ (any char):

>>

Класс символов, представляющий группу символов.

\l  строчные буквы [a-z]
\u  заглавные буквы [A-Z]
\d  цифры [0-9] 
\x  шестнадцатеричные цифры [\da-fA-F]
\s  пробелы [\t\n\r\b] 
\v  вертикальные пробелы [\n\r]
\h  горизонтальные пробелы [\b\t]
\a  обычные буквы [a-zA-Z_]
\w  слова [\a\d-]
\t  табуляция chr(9) 
\n  новая строка chr(10)
\r  возврат каретки chr(13)

Повторение rept

? может отсутствовать или существовать, один или ни одного
+ хотя бы один, возможно бесконечное количество
* может отсутствовать, но лучше больше

Группировка group: используется для переопределения приоритета правил

(a b c)+

Класс символов Char Class: ветвление символов

[abc]
[a-fA-F]
[^abc]

blank: пустота между правилами

Ниже приведены две правила, которые имеют одинаковое значение:

a -> b c
a -> b\s*c

Обработка blank очень эффективна, поэтому не стоит беспокоиться о производительности. Пробелы внутри ветвей игнорируются, они используются только для разделения токенов.

Названия токенов

Три правила названия токенов:

Правила захвата (capture Token) начинающиеся с заглавной буквы,

Захватывает успешное совпадение и добавляет его в структуру данных с ключом имени правила:

Token = 'words' 
# => ['Token','words']

Правила совпадения (match mode)

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

Token -> name
name  -> 'words'
# => ['Token','words']

Правила отклонения (reject mode)

начинающиеся с подчеркивания, автоматически отбрасывают совпадение, обычно используются для обработки комментариев:

_comment -> '#'~$

Ветвь branch:

определяет возможные варианты совпадения, каждый вариант может быть совмещен:

atom   -> |Ntoken Mtoken Ctoken|
Ntoken -> \u\a*
Mtoken -> \l\a*
Ctoken -> '_'\a*

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

Почему такая структура?

Потому что множество правил хранится как хэш, а большинство языков программирования не поддерживают порядок хэшей. Чтобы гарантировать возможность начала поиска с конкретной позиции, название этого правила было указано:

door -> 'string' rule door
rule -> "alsostr"

Каждое правило завершается переходом на новую строку, кроме правил ветвления |...|.

Имя правила может содержать '-', но не должно начинаться с '-', все указанные ниже имена правил являются легальными:

[\a\-]+  -a _a a-b A-B

Обработка невидимых символов и экранированных символов

В Spp символы отличаются от строк, символы \n \r \t должны быть экранированы, используя префикс \, код будет иметь следующий вид:

  \n \r \t \\ 

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

door    -> |\s+ _comm Spec|+ $
_comm   -> '#'~$$
Spec    -> Token '->' rule
rule    -> |Blank Branch atom|+|\v $|
Blank   -> \h+
atom    -> | Group Token Str String Kstr
       Cclass Char Chclass Assert Any Rept Till |
Branch  -> '|' | \s+ _comm atom |+ '|'
Group   -> '{' | \s+ _comm Branch atom |+ '}'
Token   -> [\a\-]+
Kstr    -> ':'[\a\-]+
Str     -> \'| [^\\']+ {\\.} |+\'
String  -> \"| [^\\"]+ {\\.} |+\"
Cclass  -> \\[adhlsuvwxADHLSUVWX]
Char    -> \\
Chclass -> \[ Flip?|\s Cclass Char Range Cchar|+ \]
Flip    -> '^'
Range   -> \w\-\w
Cchar   -> [^ \s \] \# \\ ]
Assert  -> | '^^' '$$' '^' '$' |
Any     -> '.'
Rept    -> [?*+]
Till    -> '~'

(end)