Lark, как описать серию необязательных токенов

Question

Я анализирую файл в формате, который может включать в себя:

INT32  price   min 10  max 100   alertIfSold ; 

Токены min, max и alertIfSold являются необязательными и могут отображаться в любом порядке. То есть

INT32  price    max 100   alertIfSold ; 
INT32  price  max 100   min 10    alertIfSold ;
INT32  price  alertIfSold ;
INT32  price; 

все действительные примеры.

Ниже приведена простая версия грамматики, которую я тестирую. при запуске python test.py сгенерируйте эту ошибку:

lark.common.ParseError: Обнаружена бесконечная рекурсия! (правило <__anon_star_1: __anon_star_1>)

Я пытался выразить те же дополнительные маркеры, используя другие правила грамматики, с похожими результатами (бесконечная рекурсия).

Какова правильная грамматика для выражения необязательных параметров?

#test.py
from lark import lark

simplified_grammar = """
    start: line+
    line:  TYPE  CNAME [MIN MAX ALERT]* ";"    -> foo

     TYPE: "INT32" | "INT64"

     MIN: "min" /[0-9]+/
     MAX: "max" /[0-9]+/
     ALERT: "alertIfSold"

     %import common.CNAME
     %import common.WS
     %ignore WS
  """

sample = """
    INT32  price    max 100   alertIfSold ; 
    INT32  price  max 100   min 10    alertIfSold ;
    INT32  price  alertIfSold ;
    INT32  price; 

"""

parser = lark.Lark(simplified_grammar)


def main():
    parse_tree = parser.parse(sample)

if __name__ == '__main__':
    main()

Answer 1

Ты хочешь:

line:  TYPE  CNAME (MIN | MAX | ALERT)* ";"    -> foo

(Заметка: () вместо [].)

В синтаксисе EBARF жаворонка, [item] означает "необязательный item" а также item* означает "любое число (возможно, ноль) item". Так [item]* означает "любое число (возможно, ноль) любого из item или ничего ". Но" любое количество ничего "бесконечно неоднозначно, вы не можете сказать, сколько ничего в пустой строке.

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

line:  TYPE  CNAME ([MIN] [MAX] [ALERT])* ";"    -> foo

Это было бы более точным, но это также привело бы к тому же сообщению об ошибке. В общем, вы не можете использовать звезду Клини на обнуляемом подшаблоне. Некоторые генераторы EBNF исправят это, удалив ε из повторного набора (и затем сделав повторение в целом необязательным), но lark не является одним из них. В этом случае исправление тривиально, но есть и другие случаи, в которых оно более раздражает.

Как регулярные выражения, (a* b*)*, (a? b?)* а также (a|b)* эквивалентны в том смысле, что они все признают один и тот же язык. Но регулярные выражения общеизвестно неоднозначны, и парсеры обычно предпочитают однозначные грамматики или, в худшем случае, конечно неоднозначные грамматики. В эту категорию попадает только последнее регулярное выражение, и именно эту форму вы обычно предпочитаете.