Разбор кода и построение синтаксических деревьев с PLY. Основы

[farcaller]

ply – один из лучших парсеров, с которыми я работал. Отмечу, что у рубишников есть rly, почти полный порт ply на ruby, с еще более навороченным синтаксисом (благо ruby в плане DSL потолерантнее питона). Он, правда помедленее ply, так как был допилен до уровня, достаточного чтобы я использовал его в своем проекте, но Yacc-составляющаая полноценная.

[Norty]

На фото у всех шорты мокрые, так ли страшен этот ply?

[alhimik45]

Интересная штука!
А может ли это использоваться вот в таком примере:

<?php
$foo=6;
syntax(var, ":=", val, {
var=val
});//объявили новый синтаксис
//используем
$foo := 10;

То есть в процессе парсинга грамматика может изменяться.

[xytop]

Нет. Грамматика определяется во время компилирования и не изменяется во время выполнения. Такое наверное можно сделать только руками, используя LL(1), и то, будет порождать множество неоднозначностей.

[bolk]

Вспоминается Katahdin.

[alhimik45]

Да, прикольный язык. О нём даже статья была на хабре. Хотя мне нужно compile-time изменений грамматики.

[maksbotan]

Спасибо, замечательная статья! Правда есть грамматики, для которых PLY не очень подходит, так что я перешел на простой самопальный парсер :)
Если будете продолжать писать, хотелось бы услышать про обработку ошибок.

[xytop]

хотелось бы услышать про обработку ошибок

Ну вот есть t_error и p_error — через них все и делается. В питоне ведь свойства классов динамические, так что чем больше инфы вы походу парсинга будете запихивать в t.lexer и p.parser, тем лучше будет происходить обработка.

[maksbotan]

Я в курсе про t_error и p_error, но по-человечески их завести так и не вышло. Так и не понял, как сказать красиво, например, что не закрыта какая-нибудь скобка или еще что. Как в gcc в общем.
А не подходит он для грамматики LOGO, например. Там вот это:

PRINT THING "VAR

означает это:

PRINT (THING "VAR)

Так же, как и PRINT ADD 5 THING "VAR. То есть значение имеет количество аргументов у функций.

[xytop]

По поводу скобок и всего такого, можно делать вставки в грамматику, хотя конечно не самый изящный вариант:

def p_func(p):
    '''func : expect_funcname funcname expect_lbrace LBRACE expect_body body expect_rbrace RBRACE'''
    pass

def p_expect_funcname(p): stack.push('expect funcname')
def p_expect_lbrace(p): stack.push('expect lbrace')

…

По поводу logo да, там разве что только лексер оттуда брать…

[maksbotan]

Ну это выглядит как костыль, сами понимаете.

[xytop]

Костыль, да. Но теоретически… в любых других парсерах это должно делаться примерно так же, ну т.е. мы должны как-то дать знать сами себе что ожидаем.

[xytop]

Для каких например грамматик может не подходить ply?

[impwx]

Расскажите, пожалуйста, справляется ли PLY со следующими часто встречающимися проблемами парсеров и если да, то как?

1. В статье написано, что PLY сам сортирует таблицу лексем, чтобы «побеждал длиннейший». В парсере языка C++ была проблема, что код вложенных шаблонных типов (TypeA<TypeB<TypeC>>) разбирался некорректно: две закрывающие треугольные скобки подряд воспринимались за один оператор сдвига (>>) и это приводило к ошибке синтаксиса.
2. Есть ли возможность разбирать грамматики со значащими отступами, как в самом Python?
3. Можно ли кастомизировать сообщения об ошибках? Чтобы выдавалось не нечто вроде «Ожидается: идентификатор, или число, или строка, или ...», а более подходящие по контексту: «Возможно, пропущена скобка».

[xytop]

код вложенных шаблонных типов (TypeA<TypeB>) разбирался некорректно: две закрывающие треугольные скобки подряд воспринимались за один оператор сдвига (>>)
Т.е. что-то типа этого?

string<allocator<char>> varname = "foo";

Можно просто не включать в лексер оператор '>>' и обрабатывать его в парсере, как последовательность '>'. Но тогда грамматика усложнится за счет того что придется обрабатывать ненужные пробельные символы.

2. Думаю что можно и с отступами разбирать. Посчитать их количество перед началом первого блока с отступами и считать это длиной оступа по умолчанию. В парсере мы просто считаем количество пробелов перед блоком, а затем делим на отступ по умолчанию и принимаем решение принадлежит ли блок родителю. Ну и действуем соответствующе

3. Можно. Уже ответил выше как. Нужно вставлять действия посередине.

[tzlom]

В стандарте С++ уделено внимание этой неоднозначности и решение только одно — ставить пробел, т.е. проблемный код не является валидным для С++. Но вообще С++ нельзя распарсить LALR(1) парсером, это не проблема PLY

[encyclopedist]

Теперь, с С++11, код без пробела между двумя закрывающими > в шаблонах является валидным.

[impwx]

Указание «ставить пробел» в стандарте — это классический пример ситуации «это не баг, это фича» :)

[freopen]

Кто-нибудь из тех, кто шарит в ply, объясните мне, нафига не использовать именные пространства, а вместо этого использовать префиксы к названиям переменных и функций?

[monolithed]

Зачем вы потеряли PHP_END?

[xytop]

Ну, во первых, он по спецификации не обязателен, во вторых он мне был не нужен потому что парсер кроме пыхтачка ничего не понимает.А если бы понимал, то не было бы строгого условия начинать код с <?php (можно ведь текст и вначале файла пихануть какой-то).

[xytop]

Но если хотите, могу написать через день-два, как расширить парсер на использование php как вставок… функции, классы. Хотя на самом деле это уже не будет относиться к ply напрямую, а больше к построению граматики.

[Bringoff]

Понавешали на девушку — больше всех держит.
Парсер PHP на Питоне, конечно, тооонко))

[xytop]

Ну… учитывая что есть возможность транслировать python в нативный C, это не кажется оверхедом. Если я правильно помню, то facebook делал интерпретатор php тоже на python (не hiphop, а позже какой-то там), и добились значительного ускорения.

[Bringoff]

Я имел ввиду, что это тонкий намёк на то, что пора переходить на python:-)

[shadowjack]

съинтерпретируется

Wut? Сынтерпретируется же :-)

[AlexBin]

Если не трудно, покажите примеры ветвлений.