Clever Geek Handbook

ANTLR难点：编写Ruby语法

图片在Rostelecom-Solar，我们正在开发用于漏洞和NDV的静态代码分析器，该分析器也可用于解析树。为了构建它们，我们使用ANTLR4的优化版本， 这是用于开发编译器，解释器和翻译器的工具。



该存储库包含许多编程语言的语法。但是，它缺少Ruby语法，显然没有人实现过。只有一种相似的自制语言语法，仅解析最简单的情况。这并不奇怪，因为Ruby语法难以实现，因为该语言具有非平凡的语法。但这对于那些想要编写自己的语言并考虑如何做的人来说非常有用。或者对于那些需要解决本文中讨论的技术难题的人。好吧，我们将不得不编写一个新的语法，我们将在此处进行。



ANTLR建议将语言分析分为词法分析器和解析器。



Lexer致力于根据语言字母表中给定的字符序列生成令牌。如果字符序列与多个标记的定义匹配，则选择最长的标记，并在其中选择-优先级最高的标记（由写入顺序指定）。



解析器使用从词法分析器获得的令牌（也称为终端字符）形成语言的句子（完整命令）。



通常，语法的拼写与其他语言没有什么不同。你可以学习从作者的书，资料，或者通过许多教程像这样。



在本文中，基本的实现将被省略，并且仅考虑编写上的技术困难。



Lexer问题



通常，词法分析器中唯一可能的问题是通过字符序列和附带的障碍物来发行有效令牌。



插补



一些Ruby字符串允许插值-使用语法在内部插入任意代码#{code}。例如： 



a = 3
"Hello #{if a%2==1 then "Habr!" else "World!" end}"


我们将处理模式的帮助-为特定任务设计的特定“小词法分析器”，例如我们解析字符串： 



DoubleQuote: '"' {++nestedStringLevel;}    -> pushMode(InterpolationString);


在每个嵌套级别，由于形式的原因，必须保持打开括号的数量（您需要在第二个闭合花括号处退出插值）： 



"Kappa #{
    buf = ''
    [1, 2, 3].each { |x| buf += x.to_s }
    buf
}"


为此，我们创建一个stack openedCurlyBracesInsideString。总共，我们在mod里面有一个令牌： 



StartInterpolation: '#{' {openedCurlyBracesInsideString.push(0);}    -> pushMode(DEFAULT_MODE);


现在您需要及时退出普通模式（DEFAULT_MODE），为此，我们将代码添加到令牌中： 



OpenCurlyBracket:             '{' {
    if (nestedStringLevel > 0 && !openedCurlyBracesInsideString.empty()) {
        final int buf = openedCurlyBracesInsideString.pop();
        openedCurlyBracesInsideString.push(buf + 1);
    }
};
CloseCurlyBracket:            '}' {
    if (nestedStringLevel > 0 && openedCurlyBracesInsideString.peek() <= 0) {
       popMode();
       openedCurlyBracesInsideString.pop();
    } else {
        if (!openedCurlyBracesInsideString.empty()) {
            final int buf = openedCurlyBracesInsideString.pop();
            openedCurlyBracesInsideString.push(buf - 1);
        }
    }
};


％表示法



Ruby具有受Perl启发的其他语法，用于编写字符串，字符串和符号数组（通常在Ruby中不是符号），正则表达式和shell命令。这些命令的语法为％，后跟可选的类型标识符和分隔符。例如：%w|a b c|-三个字符串组成的数组。但是，它也可用作分隔符配对的括号{} [] () <>。仅指定所有可能的标识符是行不通的-例如，序列 



q = 3
5%q


将无法正确识别。词法分析器将通过创建令牌简单地吃掉最长的字符串%q。



通过检查是否存在明显无效的分隔符（例如空格字符，数字和字母），并将其作为谓词添加到令牌中（必须在某个地方满足条件才能继续构建令牌）， 



StringArrayConstructorwToken: '%w' {canBeDelimiter()}?;


我们得到的保护几乎总是可行的（稍后会详细介绍）。我们还根据选择添加了对相应分隔符的期望。 



StartArrayConstructorNotInterpolated
    : StringArrayConstructorwToken ( Brackets {setPairDelimiter();} | ~[(<{[] {setCharDelimiter();} ) {startStringMode(ArrayConstructorw);}

fragment Brackets: '(' | '[' | '{' | '<';


其中startStringMode是用于模式切换和嵌套支持的实用程序功能。 



public void startStringMode(final int mode) {
    pushMode(mode);
    ++nestedStringLevel;
}


反例： 5%q|1 -仅在解析器的上下文中正确解析，如果已知在5个分配之后将没有字符串。



您可能会认为通过向前查找匹配的分隔符就足够了，但是这种情况有一个示例- 5%q|1|1。显然，当分为词法分析器和解析器时，无法解析这种情况。



但是，这种情况很少发生，因此\ \ _（ツ）_ /将会发生。在模式内部，我们只等待分隔符。 



ArraywWhitespace: WhitespaceAll                           -> skip;
ArraywText:       ({!isDelimiter()}? ArraywTextFragment)+ -> type(StringPart);
ArraywEnd:        . {nestedStringLevel--;}                -> type(HereDocEnd), popMode;


type为了方便起见 ，在其中更改了生成令牌的类型。



正则表达式的分割或开始



正则表达式语法如下/regexp/（以及前面提到的百分比符号）。与上一段中出现相同的解析器上下文问题，为减轻这种情况，我们创建了一个检查 



public boolean canBeRegex() {
    return isPrevWS && " \t\r\u000B\f\b\n".indexOf((char) _input.LA(1)) == -1 || isPrevNL || isOp || prevNonWsType == StartInterpolation;
}


并添加到令牌 



Divide:                       '/' {
    if (canBeRegex()) {
        startHereDoc(RegExp);
    }
};


重新计算的变量isOp，isPrevNL，isPrevWS和覆盖emit令牌的最终创作-功能 



@Override
public void emit(final Token token) {
    final String txt = token.getText();
    final int type = token.getType();
    isPrevNL = type == NL;
    isPrevWS = type == WS;
    if (!isPrevWS && !isPrevNL && type != SingleLineComment && type != MultiLineComment) {
        isOp = OPERATORS.contains(type);
        prevNonWsChar = txt.charAt(txt.length() - 1);
        prevNonWsType = type;
    }
    super.emit(token);
}


OPERATORS所有运算符的哈希图 在哪里。



解析器问题



空格字符



令人不愉快的惊喜是空格对解析的影响。通常，它们不会以任何方式影响语法，只需借助帮助将其从流中删除-> skip或翻译成另一个通道即可。但是，许多语言仍借助它们来区分某些构造。



因此，例如，a+3anda + 3不能是没有括号的函数调用，但 +3也许可以。因此，所有解析器规则如下所示（NL-换行符，WS-空格）： 



    | expression WS* op=('+' | '-') (NL | WS)* expression


为了减轻这个问题，让我们编写一个侦听器，以清除此类垃圾中的解析树。 



public class RemovingTokensListener implements ParseTreeListener {
        private List<Integer> unwantedTokens;

        ...

        @Override
        public void visitTerminal(final TerminalNode node) {
            if (this.unwantedTokens.contains(node.getSymbol().getType())) {
                ((ParserRuleContext) node.getParent().getRuleContext()).removeLastChild();
            }
        }
}


Heredoc-Lexer和解析器



用于指定多行字符串的特殊语法。可能是这样 



<<STR
content line 1
content line 2
STR


甚至是这样（有趣的是，降价无法正确识别语法）。 



value = 123
print <<STR_WITH_INTERPOLATION, <<'STR_WITHOUT_INTERPOLATION'.strip
content 1 and #{value}
STR_WITH_INTERPOLATION
     content 2 and #{value}
STR_WITHOUT_INTERPOLATION


问题在于，您需要了解行的结尾，并且方便地知道哪些内容属于哪一行。为此，请先创建一个heredocs待解析的列表（解析器根据上下文和模式可以转发任意数量的令牌） 



public final HeredocsHolder HEREDOCS = new HeredocsHolder();

public static final class HereDocEntry {
    public final String name;
    public final HereDocType type;
    public final boolean isInterpolated;
    public int partsNumber;

    public HereDocEntry(final String name, final HereDocType type, final boolean isInterpolated) {
        this.name = name;
        this.type = type;
        this.isInterpolated = isInterpolated;
        this.partsNumber = 0;
    }
}

public static final class HeredocsHolder {
    public final List<HereDocEntry> entries;
    public int toProcess;

    HeredocsHolder() {
        this.entries = new ArrayList<>();
        this.toProcess = 0;
    }
}


我们将在它们可用时添加它们 



StartHereDoc
    : HereDocToken HereDocName {
        heredocIdentifier = getHeredocIdentifier('\'');
        setText(getText().trim());
        keepHereDoc(HereDoc, false);
    }
    ;


public void keepHereDoc(final int mode, final boolean isInterpolated) {
    HEREDOCS.entries.add(new HereDocEntry(heredocIdentifier, getHereDocType(), isInterpolated));
    ++HEREDOCS.toProcess;
    isFirstNL = true;
}




此外，看到行尾有待处理的heredocs，我们称为处理函数。 



NL:                           '\n' {
    final int next = _input.LA(1);
    if (HEREDOCS.toProcess > 0 && isFirstNL) {
        startHereDocRoutine();
        isFirstNL = false;
        insideHeredoc = true;
    }
};


处理函数本身如下所示：在这里，我们仅处理最后一个heredocs（词法分析器可以继续进行，但是在这种情况下，解析器尚未吸收令牌，因此我们保存了信息） 



public void startHereDocRoutine() {
    final int stopIdx = HEREDOCS.entries.size() - HEREDOCS.toProcess;
    for (int i = HEREDOCS.entries.size() - 1; i >= stopIdx; --i) {
        if (HEREDOCS.entries.get(i).isInterpolated) {
            pushMode(HereDocInterpolated);
        } else {
            pushMode(HereDoc);
        }
    }
    nestedStringLevel += HEREDOCS.toProcess;
    currentHeredocIt = HEREDOCS.entries.listIterator(HEREDOCS.entries.size() - HEREDOCS.toProcess);
    currentHeredoc = currentHeredocIt.next();
}


需要覆盖它nextToken才能退出该模式并计算每个heredoc的令牌数量 



@Override
public Token nextToken()
{
    final CommonToken token = (CommonToken)super.nextToken();
    final int ttype = token.getType();
    if (insideHeredoc && ttype == StartInterpolation) {
        ++heredocTokensCount;
    }
    if (_mode == HereDoc || _mode == HereDocInterpolated) {
        if (ttype == VarName) {
            ++heredocTokensCount;
        } else if (ttype == StringPart) {
            ++heredocTokensCount;
            final String txt = token.getText();
            if (CheckHeredocEnd(txt)) {
                token.setText(txt.trim());
                token.setType(HereDocEnd);
                nestedStringLevel--;
                popMode();
                currentHeredoc.partsNumber = heredocTokensCount;
                if (currentHeredocIt.hasNext()) {
                    currentHeredoc = currentHeredocIt.next();
                }
                heredocTokensCount = 0;
                --HEREDOCS.toProcess;
                if (_mode == DEFAULT_MODE) {
                    insideHeredoc = false;
                }
            }
        }
    }
    return token;
}


现在让我们从解析器开始。



在帮助下，@parser::members添加到解析器：指向词法分析器的链接，我们将在其中传输其内容的字符串节点，插值节点的数量（类似于heredocTokensCount词法分析器）以及指示处理需要的语句堆栈。 



    private final RubyLexer lexer = (RubyLexer)_input.getTokenSource();
    private final List<ParserRuleContext> CONTEXTS = new ArrayList<>();
    private final List<Integer> heredocRulesCount = new ArrayList<>();
    private final Stack<StatementEntry> statements = new Stack<>();

    private static final class StatementEntry {
        public boolean needProcess;
        public int currentHeredoc;

        StatementEntry() {
            this.needProcess = false;
            this.currentHeredoc = 0;
        }
    }


让我们直接修改代码单元： 



statement
@init {
    statements.push(new StatementEntry());
}
@after {
    if (statements.peek().needProcess) {
        processHeredocs($ctx);
    }
    statements.pop();
}
    : statementWithoutHeredocTail ({statements.peek().needProcess}? interpolatedStringPart* HereDocEnd {++statements.peek().currentHeredoc;})*
    ;


@init-解析器输入规则@after时执行的代码-退出时执行的代码。



堆栈对于将heredocs分配给所需的语句是必需的，因为 内插中可能有新的。



为了正确识别heredoc可以是普通表达式并且可以将字符串视为一行中的标记的情况，以及字符串末尾位于当前表达式后面的复杂情况，我们编写以下解析器代码： 



string:
...
    | StartInterpolatedHereDoc (memberAccess* WS* NL interpolatedStringPart* HereDocEnd)? {
        if ($ctx.HereDocEnd() == null) {
            CONTEXTS.add($ctx);
            heredocRulesCount.add(0);
            statements.peek().needProcess = true;
        } else {
             lexer.HEREDOCS.entries.remove(0);
        }
    }
...


对于完全相同的插值节点计数，我们使用字符串内容修改规则代码（+ 2此处需要对打开和关闭插值的令牌进行计数） 



interpolatedStringPart
locals[int nodesCount = 0]
    : StringPart
    | VarName
    | StartInterpolation (WS* statement {++$nodesCount;})* (WS* rawStatement {++$nodesCount;})? WS* '}' {
        final int cur = statements.peek().currentHeredoc;
        if (cur < heredocRulesCount.size()) {
            heredocRulesCount.set(cur, heredocRulesCount.get(cur) + $nodesCount + 2);
        }
    }
    ;


其中locals是局部变量的列表（您需要通过引用它们$），并且不计入空格标记，因为 在我们的侦听器构建树期间将其删除。



现在让我们编写函数本身processHeredocs。让我们计算要拾取的节点数 



int heredocNodesCount = 0;
for (int i = 0; i < CONTEXTS.size(); ++i) {
    heredocNodesCount += lexer.HEREDOCS.entries.get(i).partsNumber;
    heredocNodesCount += heredocRulesCount.get(i);
}


从哪个孩子开始，我们将开始将行的内容放置在他们的位置 



int currentChild = ctx.getChildCount() - heredocNodesCount;


将内容挂钩到相应的节点 



for (int i = 0; i < CONTEXTS.size(); ++i) {
    final RubyLexer.HereDocEntry entry = lexer.HEREDOCS.entries.remove(0);
    final ParserRuleContext currentContext = CONTEXTS.get(i);
    final int currentNodesCount = entry.partsNumber + heredocRulesCount.get(i);
    for (int j = 0; j < currentNodesCount; ++j, ++currentChild) {
        final ParseTree child = ctx.getChild(currentChild);
        if (child instanceof TerminalNode) {
            ((TerminalNodeImpl) child).setParent(currentContext);
            currentContext.addChild((TerminalNodeImpl) child);
        } else if (child instanceof ParserRuleContext) {
            ((ParserRuleContext) child).setParent(currentContext);
            currentContext.addChild((ParserRuleContext) child);
        } else {
            // parser failed
            clear();
            return;
        }
    }
}


我们清除节点本身，heredoc上下文以及内插节点数列表 



for (int i = 0; i < heredocNodesCount; ++i) {
    ctx.removeLastChild();
}
clear();



private void clear() {
    CONTEXTS.clear();
    heredocRulesCount.clear();
}


最后statementWithoutHeredocTail一步是通过使用相同的侦听器将节点的子代重新挂接到其祖先，从而删除处理此文档的不必要的中间规则。 



public class RemovingRulesListener implements ParseTreeListener {
    private List<Integer> unwantedRules;

    ...

    @Override
    public void exitEveryRule(final ParserRuleContext ctx) {
        if (this.unwantedRules.contains(ctx.getRuleIndex())) {
            final ParserRuleContext parentCtx =
                    (ParserRuleContext) ctx.getParent().getRuleContext();
            parentCtx.children.remove(ctx);
            ctx.children.forEach(
                    child -> {
                        if (child instanceof RuleContext) {
                            ((RuleContext) child).setParent(parentCtx);
                            parentCtx.addChild((RuleContext) child);
                        } else if (child instanceof TerminalNode) {
                            ((TerminalNodeImpl) child).setParent(parentCtx);
                            parentCtx.addChild((TerminalNodeImpl) child);
                        }
                    }
            );
        }
    }
}


歧义性



一个尚未解决的问题是函数调用与普通加法（以及任何同时进行的一元和二进制运算的符号）之间的区别，这只能在运行时使用符号表来解决。



底线是a +a +a +a...在每个步骤的入口处都可以有普通加法和不带参数的函数调用（尽管在这种情况下，Ruby要求在第一个参数的符号后没有空格），这显然会导致沿图行走预测。



但是，仅在上下文中的一元运算符之后不允许ANTLR空间是行不通的-您必须手动重写左递归表达式，对于没有参数的情况，该表达式将自动解析。依靠“没人”无缘无故地写三十多个词这一事实，这个问题就消失了。



结论



实验上，该语法可以解析99％的文件。



因此，包含3024个红宝石文件的aws-sdk-ruby仅在7个崩溃的fastlane，在2x上包含1028的fastlane以及在2081年19月20日崩溃的Ruby on Rails崩溃。



但是，表达式中仍包含诸如heredocs之类的根本痛点 



option(:sts_regional_endpoints,
  default: 'legacy',
  doc_type: String,
  docstring: <<-DOCS) do |cfg|
Passing in 'regional' to enable regional endpoint for STS for all supported
regions (except 'aws-global'), defaults to 'legacy' mode, using global endpoint
for legacy regions.
  DOCS
  resolve_sts_regional_endpoints(cfg)
end


或用作表达式，任何块类型 



def test_group_by_with_order_by_virtual_count_attribute
    expected = { "SpecialPost" => 1, "StiPost" => 2 }
    actual = Post.group(:type).order(:count).limit(2).maximum(:comments_count)
    assert_equal expected, actual
end if current_adapter?(:PostgreSQLAdapter)


我希望本文中介绍的技术可以帮助您应对语法困难。如果您认为任何问题都可以更好地解决-欢迎发表评论。



作者：Fedor Usov，Solar appScreener开发人员


More articles:


All Articles