재귀 하강 대 Lex/파스?

필자는 (대략적으로) 재귀 적 파서 (예 : 스칼라의 파서 연결자)가 작동하는 방식을 이해한다고 생각합니다. 한 파서로 입력 문자열을 구문 분석하고 파서가 전체 입력의 각 "부분"에 대해 다른 작은 파서를 호출합니다. 입력 문자열의 조각으로부터 직접 AST를 생성하는 저수준 파서에 도달 할 때까지재귀 하강 대 Lex/파스?

또한 Lexing/Parsing 작동 방식을 이해할 수 있다고 생각합니다. 먼저 전체 입력을 플랫 목록으로 분리하는 렉서를 실행합니다. 토큰을 가져 와서 구문 분석기를 실행하여 토큰 목록을 가져와 AST를 생성합니다.

그러나 Lex/Parse 전략이 정확하게 토큰 화하는 방법이 이전에 토큰 화 된 토큰에 따라 어떻게 달라지는 지 이해할 수 없습니다. 나는 XML의 덩어리를 가지고 예를 들어, :

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>"

재귀 하강 파서가 이것을 가지고 그것을 파괴 할 수

"<tag attr='moo' omg='wtf'>attr='moo' omg='wtf'</tag>" 
    -> "<tag attr='moo' omg='wtf'>" 
     -> "<tag" 
     -> "attr='moo'" 
      -> "attr" 
      -> "=" 
      -> "moo" 
     -> "omg='wtf'" 
      -> "omg" 
      -> "=" 
      -> "wtf" 
     -> ">" 
    -> "attr='moo' omg='wtf'" 
    -> "</tag>"

그리고 (이후의 각 들여 쓰기는 상위 문자열의 분해를 나타냄) <tag, attr="moo" 등을 개별적으로 구문 분석하는 작은 파서는 XML 태그의 표현을 구성하고 속성을 추가합니다.

그러나 단일 단계 Lex/Parse는 어떻게 작동합니까? Lexer는 <tag 이후의 문자열과 > 이전의 문자열을 별도의 속성으로 토큰 화해야하며 >과 </tag> 사이의 문자열은 반드시 필요하지 않음을 어떻게 알 수 있습니까? 파서가 첫 번째 문자열이 태그 본문 내에 있고 두 번째 사례가 태그 본문 밖에 있다고 말할 필요는 없을까요?

EDIT : 그것은 명확

출처

2012-02-27 Li Haoyi

lexer는 'LEFTANGLE IDENT = tag IDENT = attr EQ STRING = moo IDENT = omg' 등을 생성합니다. –

@ SK-logic : 명확한 질문을 편집했습니다. 태그 몸체의 외부에 'attr ='moo''이 있으면 혼란 스럽습니다. 렉서가 어떻게 IDENT = 태그로 분해해서 하나의 빅 텍스트 노드로 토큰화할 수 있는지 어떻게 알 수 있습니까? –

좋아, 알 겠어. 렉서가있는 하나의 큰 문자열로 그 물건을 토큰 화하지 않을 것이다. 물론 문자열을 해체해야한다. 물론 모든 공백을 잃어 버릴 것이다. –

전형적 렉서가 "모드"또는 입력에 따라 변경 "상태"설정을 가질 것이다하도록 예 변경됨. 예를 들어, < 문자를 볼 때 모드는 "태그"모드로 변경되고 렉서는 >이 나타날 때까지 적절하게 토큰 화됩니다. 그런 다음 "내용"모드로 들어가고 렉서는 attr='moo' omg='wtf'을 모두 단일 문자열로 반환합니다. 프로그래밍 언어 렉서는, 예를 들어, 문자열 리터럴이 방법을 처리 :

string s1 = "y = x+5";

y = x+5은 수학적 표현으로 처리하지 않고 다시 문자열로 설정 않을 것입니다. "은 렉서 모드를 변경하기 때문에 문자열 리터럴로 인식됩니다.

XML 및 HTML과 같은 언어의 경우 yacc, bison 또는 ANTLR과 같은 파서 생성기 중 하나를 사용하는 것보다는 맞춤 구문 분석기를 만드는 것이 더 쉽습니다. 그들은 자동화 도구에 더 적합한 프로그래밍 언어와 다른 구조를 가지고 있습니다.

구문 분석기가 토큰 목록을 원래의 문자열로 되돌려 야하는 경우, 이는 설계에서 잘못된 점을 나타내는 기호입니다. 다른 방식으로 구문 분석해야합니다.

출처

2012-02-27 16:59:06

"상황에 맞는 토큰 화"가 필요한 이러한 언어는 렉서의 일부 구문 분석기 (렉서의 상태 머신이 파서의 상태 머신과 부분적으로 일치한다는 측면에서)를 복제해야한다고 말하는 것이 맞습니까? 당신이 렉서 국가를 많이 사용한다면 일종의 관심사 인 렉서/파서 분리를 막을 수 있습니까? 그리고 그 재귀 - 강하는 원스텝 렉싱/파싱보다 좀더 일반적입니다 (덜 멋지게 분리 되더라도)? –

보통 렉서 상태는 렉서 자체에 의해 관리됩니다. 위의 예는 그렇게 할 수 있습니다. 파서가 lexer와 통신하여 상태를 변경하는 예제가있을 것입니다. 하지만 당신의 진술에 동의합니다. 많은 일을해야한다면, 언어는 도구와 재귀 적 하강에 적합하지 않으며, 심지어 임시 파서도 좋습니다. FORTRAN이이 범주에 속한다고 생각합니다. 자동화 된 도구와 정식 구문 분석 이론보다 훨씬 앞서서 파싱하는 유일한 방법은 완전히 사용자 정의 된 파서를 사용하는 것입니다. –

답변 해 주셔서 감사합니다! 이것은 내가 "파싱 (parsing)"에 대해 물을 때 "regexs"와 "lex/yacc"또는 "tokenizer/parser"에 대해서만 들었을 때가 많았 기 때문에 특히 당황 스러웠습니다. 파서 결합 자)는 아주 단순한 경우에 더 자연스러워했습니다. 내가 미치지 않는다는 것을 아는 것이 좋다 =). –

방법>과 사이의 문자열 일 필요는 없다 동안 렉서는 반드시 후 문자열을 별도의 속성으로 토큰 화 될 것을 알고 있나요?

아니요.

는 첫 번째 문자열이 내에서 태그 본문이고, 두 번째 경우는 태그 본문 외부에 있음을 알려 파서 필요하지 않을까요?

예.

일반적으로 렉서는 입력 스트림을 토큰의 시퀀스로 바꿉니다. 토큰에는 컨텍스트가 없습니다. 즉, 토큰은 입력 스트림에서 어디에서 발생하는지에 관계없이 동일한 의미를 갖습니다. 렉싱 프로세스가 완료되면 각 토큰은 단일 단위로 처리됩니다.

XML의 경우 생성 된 렉서는 일반적으로 정수, 식별자, 문자열 리터럴 등뿐만 아니라 전체 태그가 아닌 '<'및 '>'와 같은 제어 문자를 식별합니다. 열려있는 태그, 닫는 태그, 속성, 요소 등을 이해하는 작업은 적절한 파서에 맡깁니다.

출처

2012-02-27 17:41:26

재귀 하강 대 Lex/파스?

답변

관련 문제