Как рекурсивные синтаксические анализаторы подъема работают?

Question

Как рекурсивные синтаксические анализаторы подъема работают?

, когда вы хотите показать данные из базы данных SQLIte,

private void showRadioButtonDialog() {

    // custom dialog
    final Dialog dialog = new Dialog(this);
    dialog.requestWindowFeature(Window.FEATURE_NO_TITLE);
    dialog.setContentView(R.layout.radiobutton_dialog);
    List<String> stringList=new ArrayList<>();  // here is list 

    if (cursor.moveToFirst()) {
        do {
            String a=( cursor.getString(0).toString());
            String b=(cursor.getString(1).toString());
            String c=(cursor.getString(2).toString());
            String d=(cursor.getString(3).toString());
            stringList.add(d);
        } while (cursor.moveToNext());        
    }   

    RadioGroup rg = (RadioGroup) dialog.findViewById(R.id.radio_group);

    for(int i=0;i<stringList.size();i++) {
        RadioButton rb=new RadioButton(this); // dynamically creating RadioButton and adding to RadioGroup.
        rb.setText(stringList.get(i));
        rg.addView(rb);
    }

    dialog.show();

    rg.setOnCheckedChangeListener(new RadioGroup.OnCheckedChangeListener() {

         @Override
         public void onCheckedChanged(RadioGroup group, int checkedId) {
             int childCount = group.getChildCount();
             for (int x = 0; x < childCount; x++) {
                 RadioButton btn = (RadioButton) group.getChildAt(x);
                 if (btn.getId() == checkedId) {
                     Toast.makeText(getApplicationContext(), btn.getText().toString(), Toast.LENGTH_SHORT).show();
                 }
             }
         }
     });
}

17

parsing recursion

задан Daniel O 30 May 2009 в 15:01

3 ответа

Лично мне трудно понять, как вызов функции может быть быстрее - а тем более «значительно быстрее», чем поиск в таблице. И я подозреваю, что даже «значительно быстрее» не имеет значения по сравнению со всем остальным, что должен делать лексер / парсер (в первую очередь, чтение и разметка файла). Я просмотрел страницу Википедии, но не стал следить за ссылками; действительно ли автор профилировал полный лексер / синтаксический анализатор?

Более интересным для меня является упадок парсеров, управляемых таблицами, в отношении рекурсивного спуска. Я пришел из C, где yacc (или эквивалент) был предпочтительным генератором парсеров. Когда я перешел на Java, я нашел одну реализацию, управляемую таблицами (JavaCup), и несколько реализаций рекурсивного спуска (JavaCC, ANTLR).

Я подозреваю, что ответ аналогичен ответу «почему Java вместо C»: скорость выполнения не так важна, как скорость разработки. Как отмечалось в статье в Википедии, анализаторы, управляемые таблицами, практически невозможно понять из кода (когда я их использовал, я мог следить за их действиями, но никогда не смог бы восстановить грамматику из парсера). Для сравнения: рекурсивный спуск очень интуитивно понятен (что, несомненно, объясняет, почему он старше таблично-ориентированного примерно на 20 лет).

Я мог следить за их действиями, но никогда не смог бы восстановить грамматику по синтаксическому анализатору). Для сравнения: рекурсивный спуск очень интуитивно понятен (что, несомненно, объясняет, почему он старше таблично-ориентированного примерно на 20 лет).

6

ответ дан 30 November 2019 в 14:17

Статья Википедии о рекурсивном восхождении парсинге ссылается на оригинальную статью по этой теме ("Very Fast LR Parsing"). Прочтение этой статьи прояснило для меня несколько вещей. Вот что я заметил:

В статье говорится о генерации ассемблерного кода. Интересно, можно ли сделать то же самое, что делают они, если вместо этого генерировать код на C или Java; см. разделы 4 и 5, "Восстановление ошибок" и "Проверка переполнения стека". (Я не пытаюсь охаять их технику - она может отлично работать - просто говорю, что это то, что вы, возможно, захотите рассмотреть, прежде чем принять решение)
Они сравнивают свой инструмент рекурсивного восхождения со своим собственным парсером, управляемым таблицами. Судя по описанию в разделе результатов, похоже, что их табличный парсер "полностью интерпретируемый"; он не требует никакого собственного генерируемого кода. Интересно, существует ли золотая середина, когда общая структура все еще управляется таблицами, но вы генерируете пользовательский код для определенных действий, чтобы ускорить работу?

Статья, на которую ссылается страница Википедии:

"Very fast LR parsing" (1986)
http://portal.acm.org/citation.cfm?id=13310.13326

Другая статья об использовании генерации кода вместо интерпретации таблиц:

"Very fast YACC-compatible parsers (for very little effort)" (1999)
http://www3. interscience.wiley.com/journal/1773/abstract

Также обратите внимание, что синтаксический разбор с рекурсивным спуском не является самым быстрым способом разбора языков на основе LL-грамматики:

Разница между LL и синтаксическим разбором с рекурсивным спуском?

2

ответ дан 30 November 2019 в 14:17

Другие вопросы по тегам:

parsing recursion

Похожие вопросы:

score 7 · Accepted Answer

Классическая книга дракона очень хорошо объясняет, как работают парсеры LR. Также есть Методы синтаксического анализа. Практическое руководство. где можно про них почитать, если я хорошо помню. Статья в википедии (по крайней мере, введение) не права. Они были созданы Дональдом Кнутом, и он объясняет их в своем томе 5 «Искусство компьютерного программирования». Если вы понимаете испанский, то здесь размещен полный список опубликованных мной книг . Не все книги на испанском.

Прежде чем понять, как они работают, вы должны понять несколько концепций, таких как «сначала», «после» и «вперед». Кроме того, я действительно рекомендую вам понять концепции, лежащие в основе парсеров LL (потомков), прежде чем пытаться понять парсеры LR (восходящие).

Существует семейство парсеров LR, особенно LR (K), SLR (K) и LALR (K), где K - количество опережающих просмотров, которое им нужно для работы. Yacc поддерживает синтаксические анализаторы LALR (1), но вы можете вносить поправки, не основанные на теории, чтобы заставить его работать с более мощными грамматиками.