Как написать грамматику PLY для разбора путей?

Question

Я пытаюсь написать грамматику с PLY, которая будет анализировать пути в файле. Я столкнулся с проблемами сокращения конфликтов, и я не уверен, как изменить грамматику, чтобы исправить ее. Вот пример файла, который я пытаюсь проанализировать. Путь/имя файла может быть любым допустимым контуром linux.

file : ../../dir/filename.txt 
file : filename.txt 
file : filename 

Итак, вот грамматика, которую я написал.

header : ID COLON path 

path : pathexpr filename 

pathexpr : PERIOD PERIOD DIVIDE pathexpr 
      | PERIOD DIVIDE pathexpr 
      | ID DIVIDE pathexpr 
      | 
filename : ID PERIOD ID 
      | ID    

Вот мои жетоны. Я использую библиотеку ctokens, включенную в PLY. Просто чтобы сэкономить усилия в написании моих собственных.

t_ID = r'[A-Za-z_][A-Za-z0-9_]*' 
t_PERIOD = r'\.' 
t_DIVIDE = r'/' 
t_COLON = r':' 

Так что я считаю, что есть сдвиг уменьшить конфликт в «имя файла» правила потому, что анализатор не знает, следует ли уменьшить маркер «ID» или перейти на «ID ПЕРИОДА ID». Я думаю, что есть еще одна проблема с отсутствием пути («filename»), где он будет использовать токен в pathexpr вместо сокращения до пустого.

Как я могу исправить грамматику для обработки этих случаев? Может, мне нужно изменить свои жетоны?

Answer 1

Простое решение: Используйте левые рекурсии вместо правой рекурсию.

LR-синтаксические анализаторы (как PLY и yacc) предпочитают лево-рекурсию, потому что это позволяет избежать разбора стека парсера. Он также, как правило, ближе к семантике выражения - что полезно, когда вы хотите действительно интерпретировать язык, а не просто его распознавать, и часто, как в этом случае, избегает необходимости левого фактора.

В этом случае, например, каждый сегмент пути должен быть применен к предыдущему pathexpr, ища каталог сегментов внутри текущего найденного каталога. Эффект парсера ясен: найдите $ 2 в $ 1. Как вы действуете для правильной рекурсивной версии?

Таким образом, простое преобразование:

header : ID COLON path 

path  : pathexpr filename 

pathexpr : pathexpr PERIOD PERIOD DIVIDE 
     | pathexpr PERIOD DIVIDE 
     | pathexpr ID DIVIDE 
     | 
filename : ID PERIOD ID 
     | ID 

Answer 2

Я думаю, вы можете использовать PLY, а не pyparsing, глядя на эти имена «t_xxx». Но вот Pyparsing решение вашей проблемы см ниже полезные комментарии:

""" 
header : ID COLON path 

path : pathexpr filename 

pathexpr : PERIOD PERIOD DIVIDE pathexpr 
      | PERIOD DIVIDE pathexpr 
      | ID DIVIDE pathexpr 
      | 
filename : ID PERIOD ID 
      | ID 
""" 

from pyparsing import * 

ID = Word(alphanums) 
PERIOD = Literal('.') 
DIVIDE = Literal('/') 
COLON = Literal(':') 

# move this to the top, so we can reference it in a negative 
# lookahead while parsing the path 
file_name = ID + Optional(PERIOD + ID) 

# simple path_element - not sufficient, as it will consume 
# trailing ID that should really be part of the filename 
path_element = PERIOD+PERIOD | PERIOD | ID 

# more complex path_element - adds lookahead to avoid consuming 
# filename as a part of the path 
path_element = (~(file_name + WordEnd())) + (PERIOD+PERIOD | PERIOD | ID) 

# use repetition for these kind of expressions, not recursion 
path_expr = path_element + ZeroOrMore(DIVIDE + path_element) 

# use Combine so that all the tokens will get returned as a 
# contiguous string, not as separate path_elements and slashes 
path = Combine(Optional(path_expr + DIVIDE) + file_name) 

# define header - note the use of results names, which will allow 
# you to access the separate fields by name instead of by position 
# (similar to using named groups in regexp's) 
header = ID("id") + COLON + path("path") 

tests = """\ 
file: ../../dir/filename.txt 
file: filename.txt 
file: filename""".splitlines() 

for t in tests: 
    print t 
    print header.parseString(t).dump() 
    print 

печатает

file: ../../dir/filename.txt 
['file', ':', '../../dir/filename.txt'] 
- id: file 
- path: ../../dir/filename.txt 

file: filename.txt 
['file', ':', 'filename.txt'] 
- id: file 
- path: filename.txt 

file: filename 
['file', ':', 'filename'] 
- id: file 
- path: filename 

Answer 3

Я считаю, что эта грамматика должна работать, и она имеет дополнительное преимущество, будучи в состоянии recoganize части пути, как расширение, каталог, диск и т.д. Я еще не сделал парсер, только эта грамматика.

fullfilepath : path SLASH filename 
path : root 
    | root SLASH directories 
root : DRIVE 
    | PERCENT WIN_DEF_DIR PERCENT 
directories : directory 
      | directory SLASH directories 
directory : VALIDNAME 
filename : VALIDNAME 
     | VALIDNAME DOT EXTENSION