1

我正在制作一个词法分析器和一个解析器来将一种数据格式解析为另一种数据格式(部分作为练习),我有一个问题:

假设我们有 3 种不同的数据类型,这些数据类型由它们的分隔符标识:

  1. a|b #我们称这种类型为“段”

  2. a~b #我们称这种类型为“数组”

  3. a^b #我们称这种类型为“组件”

你也可以像这样混合它们:

hey~there|how~are~you

这将对应于伪代码中的类似内容:

[["hey", "there"], ["how", "are", you"]]

hey~there^you~guy|hi|hehe

这将对应于:

[[["hey", "there"], ["you", "guy"]], "hi", "hehe"]

现在我的问题是,在我的词法分析器中,我是否会提前查看我们正在处理的数据类型,以便我可以在发出所有字符串和分隔符之前先发出令牌类型?或者我是否让解析器尝试通过它获得的分隔符来找出它?

示例hey~there^you~guy|hi|hehe

(segment)
(component)
(array)
(string "hey")
(array_delim "~")
(string "there")
(component_delim "^")
(component)
(array)
(string "you")
(array_delim "~")
(string "guy")
(segment_delim "|")
(string "hi")
(segment_delim "|")
(string "hehe")

相对

(string "hey")
(array_delim "~")
(string "there")
(component_delim "^")
(string "you")
(array_delim "~")
(string "guy")
(segment_delim "|")
(string "hi")
(segment_delim "|")
(string "hehe")

在第一种情况下,解析器会知道一个组件或数组即将到来,并提前制作正确的数据结构。在第二个示例中,它必须回溯它所做的事情,因为它稍后会弄清楚它是什么数据结构。

4

1 回答 1

1

我相信第二个示例确实是您想要使用的。从外观上看,您的语法具有以下优先级。

segments = 0
components = 1
array = 2

考虑到这一点,您可以实现Operator-precedence parser。它将像这样处理您的令牌:

shift (string "hey")
shift (array_delim "~")
shift (string "there")
reduce array1
shift array1
shift (component_delim "^") 
shift (string "you")
shift (array_delim "~")
shift  (string "guy")
reduce array2
reduce component1 
shift component1 
shift (segment_delim "|")
shift (string "hi")
reduce segment1 
shift segment1 
shift (segment_delim "|") 
shift (string "hehe")
reduce segment2
done

这将导致像这样的解析树。

segment
    segment
        component
            array
                string(hey)
                string(there)
            array
                string(you)
                string(guy)
        string(hi)
    string(hehe) 
于 2013-01-20T05:31:10.457 回答