Примеры грамматик языков программирования

Здесь приведены примеры грамматик существующих языков.

  • Грамматика языка Milan - Milan.doc
  • Грамматика языка Python - Python

В приведенных примерах грамматика указана в форме БНФ. Вам же необходимо оформить ещё в формате JSON.

Из грамматики можно выбросить все ИЛИ (использующиеся в форме БНФ). Также необходимо записать все правила в виде массивов:

{
  "<программа>": ["<объявление переменных>", "<тело программы>"],
  "<объявление переменных>": ["var", "<список переменных>"],
  "<список переменных>": ["<блок переменных>", ";", "<список переменных>"],
  "<список переменных>": ["<блок переменных>"],
  ...
}

В качестве примера описания правил генерации выходного кода предлагаю обратить внимание на проект Jison (основан на Bison). В нем каждый терминал/нетерминал в правой части описывается массивом из двух элементов. Первый элемент это собственно название терминала/нетерминала, а второй является правилом на выходном языке. Например, в выражении "JSONMember": [[ "JSONString : JSONValue", "$$ = [$1, $3];" ]] $$ обозначает нетерминал из левой части выражения JSONMember, а $1 и $3 терминалы/нетерминалы из правой части - JSONString и JSONValue. Логично предположить, что под терминалом $2 скрывается двоеточие ":". На выходе из Jison мы получаем код на JavaScript. Ниже представлен пример описания грамматики JSON в форме БНФ, и генерируемого по ней кода на JavaScript. В данном примере грамматики есть ИЛИ между разными правыми частями правил:

"bnf": {
        "JSONString": [[ "STRING", "$$ = yytext;" ]],

        "JSONNumber": [[ "NUMBER", "$$ = Number(yytext);" ]],

        "JSONNullLiteral": [[ "NULL", "$$ = null;" ]],

        "JSONBooleanLiteral": [[ "TRUE", "$$ = true;" ],
                               [ "FALSE", "$$ = false;" ]],

        "JSONText": [[ "JSONValue", "return $$ = $1;" ]],

        "JSONValue": [[ "JSONNullLiteral",    "$$ = $1;" ],
                      [ "JSONBooleanLiteral", "$$ = $1;" ],
                      [ "JSONString",         "$$ = $1;" ],
                      [ "JSONNumber",         "$$ = $1;" ],
                      [ "JSONObject",         "$$ = $1;" ],
                      [ "JSONArray",          "$$ = $1;" ]],

        "JSONObject": [[ "{ }", "$$ = {};" ],
                       [ "{ JSONMemberList }", "$$ = $2;" ]],

        "JSONMember": [[ "JSONString : JSONValue", "$$ = [$1, $3];" ]],

        "JSONMemberList": [[ "JSONMember", "$$ = {}; $$[$1[0]] = $1[1];" ],
                           [ "JSONMemberList , JSONMember", "$$ = $1; $1[$3[0]] = $3[1];" ]],

        "JSONArray": [[ "[ ]", "$$ = [];" ],
                      [ "[ JSONElementList ]", "$$ = $2;" ]],

        "JSONElementList": [[ "JSONValue", "$$ = [$1];" ],
                            [ "JSONElementList , JSONValue", "$$ = $1; $1.push($3);" ]]
    }

При генерации кода происходит банальный рекурсивный спуск по найденному на этапе синтаксического анализа дереву. Как только в очередном узле дерева будет найдено правило генерации кода в стиле $$ = [$1, $3]; в выходную строчную переменную добавляется аналогичная последовательность команд на выходном языке. Логично, что если вы делаете синтаксический анализ рекурсивным нисходящим спуском, то тогда этапы синтаксического анализа и генерации кода можно совместить вместе.

Добавить изображение из буфера обмена (Максимальный размер: 20 МБ)