Как написать 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               

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

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

Поэтому я считаю, что в правиле "имени файла" есть конфликт уменьшения сдвига, потому что анализатор не знает, следует ли уменьшить токен до "ID" или перейти к "ID PERIOD ID". Я думаю, что есть еще одна проблема со случаем отсутствия пути ("имя файла"), где он будет использовать токен в 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

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

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

Answer 3

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

"""
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