صعوبات ANTLR: كتابة قواعد روبي

في Rostelecom-Solar ، نقوم بتطوير محلل رموز ثابت لنقاط الضعف و NDV ، والذي يعمل أيضًا على تحليل الأشجار. لبنائها ، نستخدم نسخة محسنة من ANTLR4 ، وهي أداة لتطوير المجمعين والمترجمين الفوريين والمترجمين.



في مستودع يحتوي على قواعد النحو العديد من لغات البرمجة. ومع ذلك ، فإنه يفتقر إلى قواعد روبي ، والتي على ما يبدو لم ينفذها أحد. لا يوجد سوى قواعد نحوية للغة محلية الصنع مماثلة، تحليل أبسط الحالات فقط. هذا ليس مفاجئًا ، لأن قواعد روبي صعبة التنفيذ ، لأن اللغة لها بناء جملة غير تافه. ولكنه سيكون مفيدًا جدًا لأولئك الذين ، على سبيل المثال ، يريدون كتابة لغتهم الخاصة والتفكير في كيفية القيام بذلك. أو لأولئك الذين يحتاجون إلى حل الصعوبات التقنية التي تمت مناقشتها في مقالتنا. حسنًا ، علينا كتابة قواعد نحوية جديدة ، والتي سنفعلها هنا.



تقترح ANTLR تقسيم تحليل اللغة إلى lexer و parser.



تشارك 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
}"

للقيام بذلك ، لنقم بإنشاء مكدس openedCurlyBracesInsideString. في المجموع ، لدينا رمز مميز داخل التعديل:

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

لن يتم التعرف عليها بشكل صحيح. سوف يأكل lexer ببساطة أطول سلسلة أحرف عن طريق إنشاء رمز مميز %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يغير نوع الرموز التي تم إنشاؤها للراحة.

تقسيم أو بداية regex

صيغة التعبير العادي هي كما يلي /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-function من خلق النهائي للرمز

@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+3ولا a + 3يمكن أن يكون استدعاء دالة بدون أقواس ، ولكن +3ربما. لذلك ، تبدو جميع قواعد المحلل كما يلي (NL - newline ، 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 - ليكسر ومحلل

بناء جملة خاص لتحديد سلاسل متعددة الخطوط. ربما لذلك

<<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;
    }
};

وظيفة المعالجة نفسها موضحة أدناه: نحن هنا نعالج آخر محرّر هنا فقط (كان بإمكان lexer المضي قدمًا ، لكن في هذه الحالة لم يستوعب المحلل الرموز المميزة بعد ، لذلك نحفظ المعلومات)

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للخروج من الوضع وإحصاء عدد الرموز المميزة لكل مجموعة

@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أضف إلى المحلل اللغوي: رابط إلى lexer ، وعقد سلسلة حيث سننقل محتواها ، وعدد عقد الاستيفاء (عن طريق القياس مع heredocTokensCountlexer) ، بالإضافة إلى مجموعة من العبارات التي تشير إلى الحاجة إلى المعالجة.

    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...عند كل خطوة ، يمكن أن يكون هناك إضافة عادية واستدعاء دالة بدون وسيطات (على الرغم من أن روبي في هذه الحالة يتطلب عدم وجود مسافة بعد علامة الوسيطة الأولى) ، مما يؤدي على ما يبدو إلى نمو أسي للمشي على طول الرسم البياني تنبؤات.



ومع ذلك ، فإن رفض مساحة ANTLR بعد عامل تشغيل أحادي في السياق لن يعمل - سيكون عليك إعادة كتابة التعبير العودي الأيسر يدويًا ، والذي يتم حله تلقائيًا للحالة بدون وسيطات. بالاعتماد على حقيقة أن "لا أحد" يكتب أكثر من ثلاثين مصطلحًا بدون سبب ، تختفي هذه المشكلة.

خاتمة

تجريبيًا ، يمكن لهذه القواعد النحوية تحليل 99٪ من الملفات.



لذلك ، تعطل aws-sdk-ruby ، الذي يحتوي على 3024 ملفًا روبيًا ، فقط على سبعة ، المسار السريع ، الذي يحتوي على 1028 ، في 2-x ، وروبي أون ريلز من عام 2081 ، في 19



ومع ذلك ، لا تزال هناك نقاط مؤلمة بشكل أساسي مثل تلك الموجودة في التعبير

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