Как можно выразить грамматику из RFC 2396 (около URI) в PEG?

Question

Я пытаюсь придумать грамматику PEG, который разобрать имя хоста в соответствии со следующей BNF из RFC 2396

hostname  = *(domainlabel ".") toplabel [ "." ] 
    domainlabel = alphanum | alphanum *(alphanum | "-") alphanum 
    toplabel  = alpha | alpha *(alphanum | "-") alphanum 

Там нет никаких проблем с domainlabel и toplabel.

Правило для hostname Однако, похоже, не может быть выражено в ПЭГ.

Вот почему я так думаю:

Если взять грамматику, как написано в BNF весь вход потребляемую *(domainlabel "."), который не знает, когда остановиться, так как toplabel [ "." ] неотличима от него.

упрощен самодостаточная иллюстрация:

h = (d '.')* t '.'? 
d = [dt] 
t = [t] 

Это разобрать t, d.d.t и не на d.d.d который полностью ожидаемый, но он не может разобрать t. и d.d.t. которые оба являются допустимыми случаями.

Если мы добавим lookahead, тогда он будет потреблять t. и d.d.t., но сбой на d.t.t..

h = (!(t '.'?)d '.')* t '.'? 
d = [dt] 
t = [t] 

Итак, у меня нет идей, есть ли способ выразить этот BNF в PEG?

Answer 1

Если вам просто нужно проверить действительность, вы можете сделать это следующим образом:

/* Unchanged */ 
toplabel  = alpha | alpha *(alphanum | "-") alphanum 
/* Diff with above */ 
nontoplabel = digit | digit *(alphanum | "-") alphanum 
/* Rephrase */ 
hostname  = 1*(*(nontoplabel ".") toplabel) [ "." ] 

С nontoplabel и toplabel различимы их первым символом, не существует никакой возможности неоднозначности в последнем выражении.

Преобразование один из множества возможных регулярных выражений идентичностей:

(a | b)* a ==> (b* a)+ 

Вы всегда можете заменить b в a|b с b-a (с использованием - как разностный оператор набора).