詞法分析

Question

我正在做的詞法和語法分析器，以一種數據格式解析到另一個（部分作爲練習），我有一個問題：

比方說，我們有3個不同數據類型，以及這些數據類型由它們的分隔符標識：

1. A | b＃我們稱這種類型的「段」

2. A〜b＃我們稱這種類型的「陣「

3. 一個^ 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") 

在第一種情況解析器將知道組件或陣列來了，使提前正確的數據結構。在第二個例子中，它需要回溯它所做的事情，因爲它會找出它以後的數據結構。

Answer 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)