Scala CH33. 콤비네이터 파싱

아래의 글은 마틴 오더스키,렉스 스푼,빌 베너스 공저 / 오현석,이동욱,반영록 공역, 『Programming in Scala 3/e』,에이콘출판사(2017), CH01의 내용을 기반으로 작성하였습니다.

 

단파서가 필요함. 자신의 파서를 처음부터 개발하는 것

여러 파서 생성기중 하나를 사용하는 것

(파서 생성기로는Yacc, Bison, ALTLR)

(스캐너 생성기, Lex, Flex, JFlex)

내부 도메인 특화 언어

정규문법 (regular grammar), 문맥자유문법 (CFG)

 

1. 산술식

expr ::= term {"+" term | "-" term} term ::= factor {"*" factor | "/' term"} factor ::= floatingNumber | "(" expr "" import scala.util.parsing.combinator._ class Arith extends JavaTokenParsers {     def expr : Parcer[Any] = terms~rep("+"~term | "~".term)     def term : Parcel[Any] = factor~rep("*"~factor | "/"~factor)     def factor : Parser[Any] = floatingPointElement | "("~expr~")" } 산술한 파서는 한번에 요청은 follback으로 남은

1. 모든 생성 규칙은 각각 별도의 메소드가 된다.
2. 각 메소드의 결과 타입은 Parser[Any] 이다.
3. 문법에서는 순차 합성을 따로 표기하지 않지만, 프로그램에서는 ~로 명시적으로 넣어야 한다.
4. 반복은 { ... } 대신에 rep ( ... ) 로 표현한다.
5. 각 생성 규칙에 있는 마침표는 생략한다.

2. 파서실행

object ParseExpr extends Arith {     def main(args: Array[String]) = {         println("input = " + args(0))         println(parseAll(expr, args(0)))     } }

 

3. 기본 정규표현식 파서

object MyParsers extends RegexParsers {     val ident: Parser[String] = """[a-zA-Z_]\w*""".r }

 

4. JSON 파서

value ::= obj | arr | stringLiteral | floatingPointNumber | "null" | "true" | false obj ::= "{" [ members ] "}" arr ::= "[" [ values ] "]" members ::= member {"," member] member := stringLiteral ":" value value ::= value {"," value} import scala.util.parsing.combinator._ class JSON extends JavaTokenParsers {     def value : Parser[Any] = obj | arr | stringLiteral | floatingPointNumber | "null" | "true" | "false"     def obj : Parser[Any] = "{"~repsep(member, ",")~"}"     def arr : Parser[Any] = "["~repsep(value, ",")~"]"     def member : Parser[Any] = stringLiteral~":"~value } import scala.util.parsing.combinator._ class JSON1 extends JavaTokenParsers {     def obj: Parser[Map[String, Any]] = "{"~> repsep(member, ",") <~"}" ^^ (Map() ++ _)     def arr: Parser[List[Any]] = "["~> repsep(value, ",") <~ "]"     def member: Parser[(String, Any)] = stringLiteral~":"~value ^^ {case name~":"~value => (name, value)}     def value : Parser[Any] = (         obj     | arr     | stringLiteral     | floatingPointNumber ^^ (_.toDouble)     | "null" ^^ (x => null)     | "true" ^^ (x => true)     | "false" ^^ (x => false)     ) }

5. 파서의 결과

문자열 파서는 문자열 반환

정규표현식 파서도 문자열 자체 반환

순차 합성 factor ::= P~Q는 P와 Q의 결과를 모두 반환

대안 합성 P | Q 는 어느쪽이든 성공한 결과

반복 합성 req(P) repsep(P, separator) 는 P의 모든 실행에서 나온 결과를 리스트로 반환

선택적 합성 opt(P)는 스칼라 Option 타입의 인스턴스 반환

^^ 연산자는 파서 결과를 반환 P ^^ f

~  연산자의 결과는 ~  라는 이름의 케이스 클래스 인스턴스를 반환함.

"{" ~ ms ~ "}" 은 ~ ( ~ ( "{", ms), "}") 와 동일

"{" > repsep (member, ",") <~ "}" ^^ (Map() ++ _)

 

 

6. 콤비네이터 파서 규현

scala.util.parsing.combinator.Parsers 트레이트

파서타입 type Parser[T] = input => ParseResult[T]

 

파서입력

입력 : 가공되지 않은 문자 시퀀스 대신 토큰 스트림, 

type input = Reader[Elem]

Reader 클래스는 scala.util.parsing.input 패키지에 있음.

파서의 결과

sealed abstract class ParseResult[T] case class Success[T](result: T, int: Input)     extends ParseResult[T] case class Failure[T](msg: String, in: Input)     extends ParseResult[Nothing]

 

Parser 클래스

 p =>

val id = this

id.m this.m

단일 토큰 파서

elem

순차합성 ~

elem 파서는 원소를 단지 하나만 읽는다. 

대안합성 |

재귀다루기

결과반환 p ^^ f

어떤 입력도 읽지 않는 파서 : success, failure

선택적 합성과 반복합성

 

7. 문자열 리터럴과 정규표현식

문자 시퀀스만 입력으로 가능

 

8. 어휘분석과 파싱

문법분석 → 어휘 분석 하고 몇가지 종류의 토큰으로 분류

토큰의 순서를 분석하는 분법분석이 있음

scala.util.parsing.combinator.lexical

scala.util.parsing.combinator.syntactical

 

9. 오류보고

스칼라 파싱 라이브러리는 단순한 휴리스틱을 구현, 모든 실패 중에서 가장 최근의 입력 위치에서 발생한 실패를 하나 선택

 

10. 백트래킹과 LL(1)

백트래킹을 사용해 여러 대안 사이에 파서를 선택함.

백트래킹을 사용해 문법을 파싱하려면 문법을 만들대 몇가지 제한이 필요함.

왼쪽 재귀 생성 규칙을 피해야 함.

expr ::= expr "+" term | term

expr이 즉시 자기 자신을 호출하기 때문에 호출만 게속 늘어나고 어이상 진전이 없다.

expr := term "+" expr | term

(1+2) * 3 첫번째 대안 실행, + 매칭할때 실패

그리고 나서 두번째 파싱 대안 시도, 성공, 결국 term 두번 실행

expr ":= term ["+" expr]

expr ::= term {"+" term} 

많은 언어가 소위 LL(1) 이라는 문법 따름

콤비네이터 파서를 그 문법으로부터 만든다면 결코 백트래킹은 하지 않을 것

파싱 프레임워크에서 ~! 라는 연산자를 사용하면, 문법이 LL(1)이라는 사실을 명시