Skip to content

New Language Support Russian

Jump to bottom
Ivan Kochurkin edited this page Aug 9, 2018 · 5 revisions

Добавление поддержки нового языка в PT Pattern Matching (PT.PM)

Процесс работы ядра PT.PM состоит из следующих этапов:

  1. Парсинг исходного кода в дерево разбора.
  2. Преобразование дерева в унифицированный формат.
  3. Непосредственно паттерн-матчинг с пользовательскими шаблонами.

Данное разбиение предоставляет возможность описания паттернов или шаблонов под разные языки с помощью одного и того же подхода.

При добавлении нового языка (будем называть язык X) необходимо разработать первые два модуля, а именно модуль парсинга и конвертинга. Третий же модуль универсальный.

Разработка парсера

В настоящее время для парсинга всех языков кроме C# используется ANTLR-парсеры, основанные на генерации парсера из грамматик. Несмотря на то, что существуют и другие генераторы парсеров (например, yacc), лучше все же использовать ANTLR, т.к. он более популярный и уже хорошо интегрирован в PT.PM: для него написаны реализации по-умолчанию для методов Visit, VisitChildren и VisitTerminal, которые описаны в разделе Разработка конветера. Для C# же используется Roslyn-парсер. Плюсом других анализаторов являются более широкие возможности, в том числе семантический анализ. Его в будущем можно будет использовать при разработке Taint движка. При разработке парсера для нового языка целесообразно придерживаться следующей указаний:

Поиск парсера языка X работающий на платформе .NET, т.к. PT.PM написан на C#. Стоит отметить, что одним из требований движка PT.PM является обработка семантически или даже синтаксически неверного исходного кода. Если такой парсер был найден или адаптирован, и он содержит визитор для обхода деревьев разбора, то перейти к этапу Разработка конвертера, иначе попробовать поискать грамматику языка X для ANTLR в Google и в официальном репозитории грамматик grammarvs-v4. Если же грамматику найти не удалось, то перейти к этапу Разработка грамматики.

Разработка грамматики

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

  • Попытаться найти формальное описание грамматики в форме BNF, а лучше в EBNF, поскольку ANTLR поддерживает второй формат, а запись в нем получается короче и проще. Разумеется используйте EBNF формат и при написании правил в ANTLR (используйте операторы * + и ?). Если же формальное описание найти не удалось, то нужно найти хотя бы части грамматики, как это было сделано при разработке T-SQL.

  • При разработке можно пользоваться как сторонними плагинами, так и собственными наработками. Например, в PT.PM используется собственная утилита PT.PM.Prebuild для генерации парсеров при изменениях в файлах грамматик, а не на каждое их сохранение. При тестировании дерево разбора сохраняется в Lisp формате с отступами во временный файл, который затем анализируем на корректность. В текстовом файле можно искать узлы по определенным идентификатором, а также можно делать diff для двух деревьев, чего не сделаешь в графическом.

    Пример кода на PHP 
    <?php
try {
    echo 1/0;
} catch (Exception $e) {
}
?>
    Список токенов 
    Try (try)
OpenCurlyBracket ({)
Echo (echo)
Decimal (1)
Divide (/)
Decimal (0)
SemiColon (;)
CloseCurlyBracket (})
Catch (catch)
OpenRoundBracket (()
Label (Exception)
VarName ($e)
CloseRoundBracket ())
OpenCurlyBracket ({)
CloseCurlyBracket (})
SemiColon (?>)
EOF
    Дерево разбора 
    (
htmlDocument
(
htmlElementOrPhpBlock
    (
    phpBlock
    (
    topStatement
        (
        nonEmptyStatement
        (
        tryCatchFinally
            'try'
            (
            blockStatement
            '{'
            (
            innerStatementList
                (
                innerStatement
                (
                statement
                    (
                    nonEmptyStatement
                    (
                    echoStatement
                        'echo'
                        (
                        expressionList
                        (
                        expression
                            (
                            expression
                            (
                            constant
                                (
                                literalConstant
                                (
                                numericConstant
                                    '1'
                                )
                                )
                            )
                            )
                            '/'
                            (
                            expression
                            (
                            constant
                                (
                                literalConstant
                                (
                                numericConstant
                                    '0'
                                )
                                )
                            )
                            )
                        )
                        )
                        ';'
                    )
                    )
                )
                )
            )
            '}'
            )
            (
            catchClause
            'catch'
            '('
            (
            qualifiedStaticTypeRef
                (
                qualifiedNamespaceName
                (
                namespaceNameList
                    (
                    identifier
                    'Exception'
                    )
                )
                )
            )
            '$e'
            ')'
            (
            blockStatement
                '{'
                (
                innerStatementList
                )
                '}'
            )
            )
        )
        )
    )
    (
    topStatement
        (
        emptyStatement
        '?>'
        )
    )
    )
)
'EOF'
)

  • Однако плагины также разумно использовать. Сейчас существуют следующие плагины для работы с ANTLR грамматиками:

    • Пожалуй самый известный и функциональный плагин от автора ANTLR ANTLR v4 grammar plugin, которые поддерживает подсветку синтаксиса и ошибок, рефакторинг, тестирование корректности парсинга и неоднозначностей, построение дерева разбора и многие другие. Однако для него требуется установленная IDEA, и он больше ориентирован на Java платформу.
    • Плагин ANTLR Language Support к текстовому редактору Visual Code.

  • Старайтесь использовать как можно меньше правил, но не меньше, чем нужно, потому что надо также избегать дублирования. Каждое правило порождает лишний вызов метода в парсере, и для парсинга длинных рекурсивных выражений может не хватить стека. Также это влияет на производительность.

  • Как следствие из прошлого пункта - старайтесь переписывать обычные правила в леворекурсивные, если это возможно. В ANTLR 4.6 исправили проблему парсинга глубоких рекурсивных выражений.

    • Обычные правила
    expression
    : multExpression
    | expression ('+'|'-') multExpression
    ;

multExpression
    : ID
    | multExpression ('*'|'/') ID
    ;
    • Правила, преобразованные в одно леворекурсивное правило
    expression
    : expression ('*'|'/') expression
    | expression ('+'|'-') expression
    | ID
    ;

  • Публикуйте грамматики в официальном репозитории под лицензией MIT или Apache. Обязательно добавляйте примеры корректного кода для тестов в подпапку examples, а также придерживайтесь стандартного Code Style при разработке.

Подробнее о разработке ANTLR грамматик можно узнать в статье "Теория и практика парсинга исходников с помощью ANTLR и Roslyn" в разделе От теории к практике. Там рассматриваются PHP, T-SQL и PL/SQL.

Разработка конвертера

Для преобразования дерева разбора в универсальное синтаскическое дерево (UST) используется паттер Visitor. В нем необоходимо переопределить методы Visit для всех правил грамматики. Однако это может быть слишком муторно и бесполезно. Поэтому для не интересующих узлов может использоваться метод VisitChildren по-умолчанию, который создает искусственные узлы MultichildExpression при необходимости. Также при обходе терминальных (конечных) узлов, используется реализация по-умолчанию для метода VisitChildren, в которой производится попытка распознавания типа литерального узла (String, Float, Int и т.д.).

Более подробно об этих методах написано в документе API в разделе "Вспомогательные классы ANTLR" и статье Обработка древовидных структур и унифицированное AST. Также целесообразно ознакомиться с его реализацией в репозитории PT.PM.

Правило ifStatement 
ifStatement
    : If parenthesis statement elseIfStatement* elseStatement?
    | If parenthesis ':' innerStatementList elseIfColonStatement* elseColonStatement? EndIf ';'
    ;
Пример метода VisitIfStatement для правила ifStatement 
public UstNode VisitIfStatement(PHPParser.IfStatementContext context)
{
    var condition = (Expression)Visit(context.parenthesis());
    Statement trueStatement;
    List<IfElseStatement> ifElseStatements;
    Statement elseStatement = null;
    if (context.statement() != null)
    {
        trueStatement = (Statement)Visit(context.statement());
        ifElseStatements = context.elseIfStatement()
            .Select(statement => (IfElseStatement)Visit(statement))
            .Where(statement => statement != null).ToList();
        if (context.elseStatement() != null)
        {
            elseStatement = (Statement)Visit(context.elseStatement());
        }
    }
    else
    {
        trueStatement = (Statement)Visit(context.innerStatementList());
        ifElseStatements = context.elseIfColonStatement()
            .Select(statement => (IfElseStatement)Visit(statement))
            .Where(statement => statement != null).ToList();
        if (context.elseColonStatement() != null)
        {
            elseStatement = (Statement)Visit(context.elseColonStatement());
        }
    }

    var result = new IfElseStatement(condition, trueStatement, context.GetTextSpan(), FileNode);
    IfElseStatement s = result;
    foreach (var elseIfStatement in ifElseStatements)
    {
        s.FalseStatement = elseIfStatement;
        s = elseIfStatement;
    }
    s.FalseStatement = elseStatement;
    return result;
}
UST в формате Json для примера кода на PHP выше 
{
  "NodeType": "FileNode",
  "FileName": {
    "NodeType": "StringLiteral",
    "Text": "Source Code"
  },
  "Root": {
    "NodeType": "NamespaceDeclaration",
    "Name": {
      "NodeType": "StringLiteral",
      "Text": "root"
    },
    "Members": [
      {
        "NodeType": "NamespaceDeclaration",
        "Name": {
          "NodeType": "StringLiteral",
          "Text": "pt.pm_default"
        },
        "Members": [
          {
            "NodeType": "BlockStatement",
            "Statements": [
              {
                "NodeType": "TryCatchStatement",
                "TryBlock": {
                  "NodeType": "BlockStatement",
                  "Statements": [
                    {
                      "NodeType": "ExpressionStatement",
                      "Expression": {
                        "NodeType": "InvocationExpression",
                        "Target": {
                          "NodeType": "IdToken",
                          "Id": "echo"
                        },
                        "Arguments": {
                          "NodeType": "ArgsNode",
                          "Collection": [
                            {
                              "NodeType": "BinaryOperatorExpression",
                              "Left": {
                                "NodeType": "IntLiteral",
                                "Value": 1
                              },
                              "Operator": {
                                "NodeType": "BinaryOperatorLiteral",
                                "BinaryOperator": "Divide"
                              },
                              "Right": {
                                "NodeType": "IntLiteral"
                              }
                            }
                          ]
                        }
                      }
                    }
                  ]
                },
                "CatchClauses": [
                  {
                    "NodeType": "CatchClause",
                    "Type": {
                      "NodeType": "TypeToken",
                      "TypeText": "Exception"
                    },
                    "VarName": {
                      "NodeType": "IdToken",
                      "Id": "e"
                    },
                    "Body": {
                      "NodeType": "BlockStatement",
                      "Statements": []
                    }
                  }
                ]
              },
              {
                "NodeType": "EmptyStatement"
              }
            ]
          }
        ],
        "Language": "Php"
      }
    ],
    "Language": "Php"
  }
}

Тестирование

При работе PT.PM использует шаблоны, которые можно задавать как в коде (на C#), так и с помощью разработанного предметно-ориентированного язык DSL, описание которого можно также найти в документе DSL.

В настоящий момент тестировать движок PT.PM можно следующими способами:

Программный способ

Несмотря на то, что это не слишком удобно, и проблематично для не разработчиков, с помощью данного способа можно описывать паттерны непосредственно в коде. Модуль PT.PM имеет открытый исходный код и его можно подключать как NuGet пакет из источника https://ci.appveyor.com/nuget/pt-pm-mk0aj1y5uned. С архитектурой и подробным описанием классов можно ознакомиться в API.

PT.PM.Cli

Представляет собой консольное приложение. Подробное описание всех параметров описано в документе Cli. Обновляется часто, т.к. собирается автоматически с помощью CI системы.

PT.PM.Gui

Кроссплатформенная утилита на базе UI-фреймворка Avalonia для разработчиков, позволяющая загружать базу с шаблонами и тестировать ее на реальном коде. Помимо непосредственного сопоставления с шаблонами, эта программа позволяет тестировать все три этапа Workflow: парсинг, преобразование и сопоставление. При необходимости возможно отображение токенов, дерева разбора ANTLR и универсального дерева в формате JSON. Недостатком является непроработанный интерфейс. Версии выходят часто, т.к. тоже собирается с помощью CI системы, как и PT.PM.Cli.

Approof

Официальное WPF Windows приложение, в которое встроена функциольность движков PT.PM, PT.Fingerprint и движка по сборке статистики для различных проектов PT.SourceStats. Имеет проработанный интерфейс, однако предназначено для обычных пользователей и не позволяет тестировать отдельные этапы работы PT.PM.

Clone this wiki locally