LL (1) 파서가 스택으로 구현되었습니다. AST를 작성하는 방법은 무엇입니까?

Question

저는 현재 손으로 파서를 만들고 있습니다. LL (1) 파서입니다. 현재로서는 위대한 인식 자입니다. 함수 구문 분석 (목록 토큰)은 토큰이 언어의 구성원인지 여부를 결정합니다.

이제 해당 입력에 해당하는 AST를 작성하려고합니다. 그러나, 나는 그것을 재귀 하강 방식으로 구현하는 방법을 이미 알고있다. 즉, 도전, 나는 고전적인 알고리즘을 사용하여 스택을 사용하여 내 스택을 구현하는 경우 : PARSING_TABLE은 LL (1) 테이블

next <- first token of the input 
stack <- START_SYMBOL 
do { 
    top <- stack.pop() 
    if (top is a terminal and top == next) { 
     next <- next token of the input 
    } else if (top is a non terminal and PARSING_TABLE[top, next] exists) { 
     stack.push(PARSING_TABLE[top, next]); 
    } else { 
     return invalid input; 
    } 
} while (stack is not empty); 
return valid input; 

합니다. 그러나 이러한 구성에서 AST를 작성하는 부분을 구현하는 방법을 궁금합니다. 완전한 구현을 요구하지는 않습니다. 구현 아이디어가 더 필요합니다.

감사합니다.

Answer 1

가

내 initial stack <- START_SYMBOL 저장할 수있는 주석 (즉 규칙 번호 + 위치 규칙 + 대상 데이터 저장) + (단자/비 단자)이 AST 항목 참조가 포함되도록 스택은 주석 될 수있는 그 AST 루트가됩니다.

기본적으로 pop()은 현재 AST 구성을 선택합니다. 그런 다음 next <- next token은 AST에 값을 저장합니다. stack.push(PARSING_TABLE[top, next]);은 새 AST 목록을 열고 top에 해당하는 구문에 쓰고 스택의 각 항목에 '규칙 번호 + 위치 + 대상 목록'을 생성합니다.

구문 분석이 완료되면 전체 트리가 생성됩니다.

정확한 AST에서는 일부 토큰을 무시할 수 있습니다. 이 작업은 push() 부분에서 스택 세트의 적절한 주석을 통해 수행 할 수 있습니다. 일반적인 방법은 각 규칙 (A -> B C)에 몇 가지 메타 정보를 첨부하는 것입니다 (예 : 보존 대상과 결과의 본질).

Answer 2

스택의 비단 말을 일치 규칙의 rhs로 바꾸는 일반적인 방법이 예측 된 순간에 효과적으로 문법 구조를 잊어 버리기 때문에 어려움이 발생합니다. 그러나 AST를 생성하려면 나중에 규칙 구문 분석이 완료 될 때 해당 구조가 필요합니다.

nonterminal을 일치 규칙의 rhs 기호로 바꾸는 대신 해당 위치에 그대로두고 일치하는 기호를 목록 개체로 푸시합니다. 이 방법은 스택이 문법의 계층 구조를 유지합니다.

구문 분석은 맨 위 목록의 기호를 사용합니다. 목록의 고갈은 규칙의 완료에 해당합니다. 비 터미널은 규칙이 완료 될 때 스택에서 제거되며 예측할 때 제거되지 않습니다.

스택이 소비됨에 따라 관련 규칙을 기억하고 구문 분석 된 토큰을 저장하는 결론적 인 AST 구조를 작성하십시오. 따라서 스택은 구문 분석 된 AST로 흐르는 예측 된 AST와 같은 역할을합니다.

이것은 심볼 목록 스택을 호출 프레임 스택으로 사용하여 재귀 - 하강 파서의 호출 계층을 에뮬레이트하는 것으로 생각할 수 있습니다. 루비에서

:

이

# g is the grammar; a list of rules 
# s is a terminal sequence to parse 
# note, this code does not tokenize EOF 

def parse(g, s) 

tab = gen_table(g) 
stack = [[g.start_sym]] 
# intermediate ast node format: [rule-action, symbols...] 
ast = [[->(rhs){[:_S, rhs[0]]}]] 

loop do 
    puts "PARSE\n #{s}\n #{stack}\n #{ast}" 

    if stack.first.empty? 
    raise "extraneous input" if not s.empty? 
    break 
    end 

    if stack.last.empty? # rule complete 
    stack.pop 
    node = ast.pop 
    # transform the node (eg to a class) using the associated rule-action 
    node = node.first.(node.drop(1)) 
    ast.last.push(node) 
    stack.last.shift # rm sym from stack after completing it 
    next 
    end 

    raise "incomplete input" if s.empty? 
    tok = s.first 
    topsym = stack.last.first 

    if topsym.is_a? String # terminal 
    raise "mismatch #{tok} != #{topsym}" if tok != topsym 
    stack.last.shift 
    ast.last.push(s.shift) 

    elsif topsym.is_a? Symbol # nonterminal 
    ri = tab[topsym][tok] 
    raise "no rule for #{topsym}, #{tok}" if ri.nil? 
    stack.push(g[ri].rhs.clone) 
    ast.push([g[ri].action]) 
    end 

end 

node = ast.first 
node.first.(node.drop(1)) 
end