9

我正在尝试创建一个语法来解析我设计的一些类似 Excel 的公式，其中字符串开头的特殊字符表示不同的来源。例如，$可以表示一个字符串，因此“ $This is text”在程序中会被视为字符串输入，并且&可以表示函数，因此&foo()可以被视为对内部函数的调用foo。

我面临的问题是如何正确构建语法。例如，这是作为 MWE 的简化版本：

grammar = r'''start: instruction

?instruction: simple
            | func

STARTSYMBOL: "!"|"#"|"$"|"&"|"~"
SINGLESTR: (LETTER+|DIGIT+|"_"|" ")*
simple: STARTSYMBOL [SINGLESTR] (WORDSEP SINGLESTR)*
ARGSEP: ",," // argument separator
WORDSEP: "," // word separator
CONDSEP: ";;" // condition separator
STAR: "*"
func: STARTSYMBOL SINGLESTR "(" [simple|func] (ARGSEP simple|func)* ")"

%import common.LETTER
%import common.WORD
%import common.DIGIT
%ignore ARGSEP
%ignore WORDSEP
'''
parser = lark.Lark(grammar, parser='earley')

所以，使用这个语法，像: $This is a string, &foo(), &foo(#arg1), &foo($arg1,,#arg2)and&foo(!w1,w2,w3,,!w4,w5,w6)这样的东西都会按预期进行解析。但是，如果我想为我的simple终端增加更多的灵活性，那么我需要开始摆弄SINGLESTR不方便的令牌定义。

我试过什么

我无法超越的部分是，如果我想要一个包含括号的字符串（它们是 的文字func），那么在我目前的情况下我无法处理它们。

  • 如果我在 中添加括号SINGLESTR，那么我会得到Expected STARTSYMBOL，因为它与定义混淆了，func它认为应该传递一个函数参数，这是有道理的。
  • 如果我重新定义语法以仅为函数保留 & 符号并在 中添加括号SINGLESTR，那么我可以解析带括号的字符串，但我尝试解析的每个函数都会给出Expected LPAR.

我的意图是任何以 a 开头的东西$都会被解析为一个SINGLESTR标记，然后我可以解析像&foo($first arg (has) parentheses,,$second arg).

目前，我的解决方案是在我的字符串中使用 LEFTPAR 和 RIGHTPAR 之类的“转义”词，并且在处理树时我已经编写了辅助函数来将它们更改为括号。因此，$This is a LEFTPARtestRIGHTPAR生成正确的树，当我处理它时，它会被转换为This is a (test).

提出一个一般性问题：我能否以这样一种方式定义我的语法，即某些语法特殊的字符在某些情况下被视为正常字符而在任何其他情况下被视为特殊字符？

编辑 1

根据jbndlr我修改语法以创建基于开始符号的单独模式的评论：

grammar = r'''start: instruction

?instruction: simple
            | func

SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"("|")")*
FUNCNAME: (LETTER+) (LETTER+|DIGIT+|"_")* // no parentheses allowed in the func name
DB: "!" SINGLESTR (WORDSEP SINGLESTR)*
TEXT: "$" SINGLESTR
MD: "#" SINGLESTR
simple: TEXT|DB|MD
ARGSEP: ",," // argument separator
WORDSEP: "," // word separator
CONDSEP: ";;" // condition separator
STAR: "*"
func: "&" FUNCNAME "(" [simple|func] (ARGSEP simple|func)* ")"

%import common.LETTER
%import common.WORD
%import common.DIGIT
%ignore ARGSEP
%ignore WORDSEP
'''

这（有点）属于我的第二个测试用例。我可以解析所有simple类型的字符串（可以包含括号的 TEXT、MD 或 DB 标记）和空函数；例如，&foo()或&foo(&bar())正确解析。在我将参数放入函数中的那一刻（无论哪种类型），我都会得到一个UnexpectedEOF Error: Expected ampersand, RPAR or ARGSEP. 作为概念证明，如果我在上面的新语法中从 SINGLESTR 的定义中删除括号，那么一切正常，但我又回到了原点。

4

2 回答 2

3 
import lark
grammar = r'''start: instruction

?instruction: simple
            | func

MIDTEXTRPAR: /\)+(?!(\)|,,|$))/
SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"("|MIDTEXTRPAR)*
FUNCNAME: (LETTER+) (LETTER+|DIGIT+|"_")* // no parentheses allowed in the func name
DB: "!" SINGLESTR (WORDSEP SINGLESTR)*
TEXT: "$" SINGLESTR
MD: "#" SINGLESTR
simple: TEXT|DB|MD
ARGSEP: ",," // argument separator
WORDSEP: "," // word separator
CONDSEP: ";;" // condition separator
STAR: "*"
func: "&" FUNCNAME "(" [simple|func] (ARGSEP simple|func)* ")"

%import common.LETTER
%import common.WORD
%import common.DIGIT
%ignore ARGSEP
%ignore WORDSEP
'''

parser = lark.Lark(grammar, parser='earley')
parser.parse("&foo($first arg (has) parentheses,,$second arg)")

输出：

Tree(start, [Tree(func, [Token(FUNCNAME, 'foo'), Tree(simple, [Token(TEXT, '$first arg (has) parentheses')]), Token(ARGSEP, ',,'), Tree(simple, [Token(TEXT, '$second arg')])])])

我希望这是你要找的。

这几天真是太疯狂了。我尝试了百灵鸟，但失败了。我也试过persimonious和pyparsing。所有这些不同的解析器都存在相同的问题，即“参数”令牌消耗作为函数一部分的右括号，最终失败，因为函数的括号没有关闭。

诀窍是弄清楚如何定义“不特殊”的右括号。请参阅上面代码中的正则表达式MIDTEXTRPAR。我将其定义为右括号，后面没有参数分隔或字符串结尾。我通过使用正则表达式扩展来做到这一点，该扩展(?!...)仅在它后面...没有但不消耗字符时才匹配。幸运的是，它甚至允许在这个特殊的正则表达式扩展中匹配字符串的结尾。

编辑：

上述方法仅在您没有以 ) 结尾的参数时才有效，因为 MIDTEXTRPAR 正则表达式不会捕捉到 ) 并且会认为这是函数的结尾，即使有更多参数要处理。此外，可能存在歧义，例如 ...asdf),,...，它可能是参数内函数声明的结尾，或参数内的 'text-like' ) 并且函数声明继续。

这个问题与您在问题中描述的不是上下文无关语法（https://en.wikipedia.org/wiki/Context-free_grammar）有关，其中存在诸如 lark 之类的解析器。相反，它是一种上下文相关的语法（https://en.wikipedia.org/wiki/Context-sensitive_grammar）。

它是上下文敏感语法的原因是因为您需要解析器“记住”它嵌套在一个函数中，以及嵌套的级别，并以某种方式在语法的语法中使用此内存。

编辑2：

另请查看以下上下文相关的解析器，它似乎可以解决问题，但嵌套函数的数量具有指数时间复杂度，因为它会尝试解析所有可能的函数障碍，直到找到一个可行的障碍。我相信它必须具有指数复杂性，因为它不是上下文无关的。


_funcPrefix = '&'
_debug = False

class ParseException(Exception):
    pass

def GetRecursive(c):
    if isinstance(c,ParserBase):
        return c.GetRecursive()
    else:
        return c

class ParserBase:
    def __str__(self):
        return type(self).__name__ + ": [" + ','.join(str(x) for x in self.contents) +"]"
    def GetRecursive(self):
        return (type(self).__name__,[GetRecursive(c) for c in self.contents])

class Simple(ParserBase):
    def __init__(self,s):
        self.contents = [s]

class MD(Simple):
    pass

class DB(ParserBase):
    def __init__(self,s):
        self.contents = s.split(',')

class Func(ParserBase):
    def __init__(self,s):
        if s[-1] != ')':
            raise ParseException("Can't find right parenthesis: '%s'" % s)
        lparInd = s.find('(')
        if lparInd < 0:
            raise ParseException("Can't find left parenthesis: '%s'" % s)
        self.contents = [s[:lparInd]]
        argsStr = s[(lparInd+1):-1]
        args = list(argsStr.split(',,'))
        i = 0
        while i<len(args):
            a = args[i]
            if a[0] != _funcPrefix:
                self.contents.append(Parse(a))
                i += 1
            else:
                j = i+1
                while j<=len(args):
                    nestedFunc = ',,'.join(args[i:j])
                    if _debug:
                        print(nestedFunc)
                    try:
                        self.contents.append(Parse(nestedFunc))
                        break
                    except ParseException as PE:
                        if _debug:
                            print(PE)
                        j += 1
                if j>len(args):
                    raise ParseException("Can't parse nested function: '%s'" % (',,'.join(args[i:])))
                i = j

def Parse(arg):
    if arg[0] not in _starterSymbols:
        raise ParseException("Bad prefix: " + arg[0])
    return _starterSymbols[arg[0]](arg[1:])

_starterSymbols = {_funcPrefix:Func,'$':Simple,'!':DB,'#':MD}

P = Parse("&foo($first arg (has)) parentheses,,&f($asdf,,&nested2($23423))),,&second(!arg,wer))")
print(P)

import pprint
pprint.pprint(P.GetRecursive())
于 2019-11-30T19:48:30.733 回答
1

问题是函数的参数包含在括号中，其中一个参数可能包含括号。
一种可能的解决方案是当它是 String 的一部分时，在 ( 或 ) 之前使用退格 \

  SINGLESTR: (LETTER+|DIGIT+|"_"|" ") (LETTER+|DIGIT+|"_"|" "|"\("|"\)")*

C 使用的类似解决方案，包括双引号（“）作为字符串常量的一部分，其中字符串常量用双引号引起来。

  example_string1='&f(!g\()'
  example_string2='&f(#g)'
  print(parser.parse(example_string1).pretty())
  print(parser.parse(example_string2).pretty())

输出是

   start
     func
       f
       simple   !g\(

   start
     func
      f
      simple    #g
于 2019-11-28T06:34:45.900 回答