effbot.org ::: zone ::: Using Regular Expressions for Lexical Analysis
Think this article can be improved? Check for comments, or add your own!

정규 표현식으로 어휘 분석하기

February 04, 2002 | Fredrik Lundh
한글판 johnsonj 2007.03.28

이 글은 어휘 분석에 파이썬 2.0이상의 re 모듈을 사용하는 법을 연구한다.

간단한 RE 스캐너

스캐너는 입력 문자열(예, 프로그램 코드)을 읽어 문자들을 어휘 단위로 그룹짓는다. 예를 들어, 키워드와 정수 기호상수와 같은 단위로 말이다. 스캐너는 또한 어휘 분석기 또는 토큰 생성기로 알려져 있다.

예를 들어, 다음은 간단한 표현식이다:

b = 2 + a*10

위의 표현식에서, 세 개의 토큰 유형을 식별할 수 있다:

정규 표현식은 간단한 스캐너를 작성하는데 쉽고 강력한 도구를 제공한다. 예를 들어, findall 메쏘드를 사용하여 표현식을 토큰 리스트로 분리할 수 있다:

# File: xml-scanner-example-1.py

import re

expr = "b = 2 + a*10"

print re.findall("\s*(\d+|\w+|.)", expr)

패턴이 앞에 있는 공백들을 건너뛴다는 사실을 주목하자. 토큰 패턴은 모두 같은 그룹에 배치된다. 그래서 findall은 눈에 보이는 그대로 토큰 문자열 리스트를 돌려준다:

$ python xml-scanner-example-1.py
['b', '=', '2', '+', 'a', '*', '10']

다음 단계는 토큰 리스트를 그 표현식을 해석할 줄 아는 함수에 건넨다 (또는 실행가능 코드 같은 것으로 컴파일할 수도 있다).

여기에서 문제는 findall이 토큰 리스트를 돌려주고, 프로그램은 각 토큰을 검열해서 실제로 그것이 무엇인지 알아 보아야 한다. 예를 들어 첫 문자를 살펴 보고; 그것이 숫자이면, 토큰은 정수 기호상수를 나타낸다. 기호 또는 밑줄문자라면, 토큰은 심볼을 나타낸다. 다른 모든 토큰은 잠재적인 연산자이다.

다음의 추가 점검은 별로 필요할 듯하지 않다; 어쨋거나, 정규 표현식 엔진은 어떤 서브패턴을 골랐는지 안다. 이 정보를 얻는 방법 하나는 토큰 서브패턴 하나하나가 그의 그룹 안에 있도록 그 패턴을 수정하는 것이다.

# File: xml-scanner-example-2.py

import re

expr = "b = 2 + a*10"

for item in re.findall("\s*(?:(\d+)|(\w+)|(.))", expr):
    print item

이 경우, 하나 이상의 그룹이 패턴에 있으면, findall은 일치하지 않는 그룹에 대하여 빈 문자열을 가진 터플을 돌려준다:

$ python xml-scanner-example-2.py
('', 'b', '')
('', '', '=')
('2', '', '')
('', '', '+')
('', 'a', '')
('', '', '*')
('10', '', '')

토큰 유형을 발견하려면, 각 터플에서 비어있지-않은 첫 항목을 찾으면 된다. 예를 들어:

if item[0]:
    print "integer", item[0]
elif item[1]:
    print "symbol", item[1]
else:
    print "operator", item[2]

이 해결책은 다른 토큰 유형이 너무 많지만 않다면 아주 잘 작동하지만, 숫자가 증가하면 즉시 망가진다.

실제로 파이썬 2.0 이상에서 그룹 인덱스를 얻는 방법이 있다. 정규 표현식 엔진이 그룹을 완료하면, lastindex라고 부르는 정수 레지스터에 그룹 번호를 할당한다. 성공적으로 일치하면, 이 레지스터는 match object의 속성에서 얻을 수 있다 ( match 또는 search 호출이 성공적이면 반환되는 객체).

유일한 문제는 여기에서 findall이 일치 객체가 아니라, 문자열 (또는 터플)을 돌려준다는 것이다. 이런, 독자적으로 스캐닝 회돌이를 작성할 필요가 있겠다:

# File: xml-scanner-example-3.py

import re

expr = "b = 2 + a*10"

pos = 0

pattern = re.compile("\s*(?:(\d+)|(\w+)|(.))")

while 1:
    m = pattern.match(expr, pos)
    if not m:
        break
    print m.lastindex, repr(m.group(m.lastindex))
    pos = m.end()
$ python xml-scanner-example-3.py
2 'b'
3 '='
1 '2'
3 '+'
2 'a'
3 '*'
1 '10'

여기에서, lastindex 속성은 정수에 대하여 1, 심볼에 대하여 2, 연산자에 대하여 코드가 3이다.

주의: 최근 버전에서는 findall 대신에 finditer를 사용할 수 있다. finditer는 내부 스캐너 객체를 사용하여 일치 객체를 게으르게 구성된 연속열로 돌려준다(아래 참조).

2.0 엔진은 이것을 훨씬 더 최적화하는데 사용이 가능한 또다른 (비문서화된) 특징을 제공한다. scanner 메쏘드는 scanner object를 만들어서 그것을 문자열에 붙이는데 사용할 수 있다. 이 객체는 현재 위치를 추적유지하고 성공적으로 일치(match)가 될 때마다 앞으로 나아간다. 손수 위치를 추적유지하는 대신에, 그냥 스캐너를 부르고 또 부르면 된다.

pos 변수를 스캐너 객체로 교체하고 난 후에, 우리 예제는 이제 다음과 같이 보인다:

# File: xml-scanner-example-4.py

import re

expr = "b = 2 + a*10"

pos = 0

pattern = re.compile("\s*(?:(\d+)|(\w+)|(.))")

scan = pattern.scanner(expr)

while 1:
    m = scan.match()
    if not m:
        break
    print m.lastindex, repr(m.group(m.lastindex))

약간 더 복잡한 RE 스캐너

약간 더 큰 예제를 살펴보자: 빠르지만 좀 허접한 XML 해석기이다.

XML 문서는 태그와 개체 그리고 문자 데이터 섹션으로 구성된다. 태그는 상대적으로 복잡한 객체이다; 시작 태그는 시작을 알리는 좌꺽쇠와 식별자(요소 이름) 그리고 선택적 속성과 끝을 알리는 우꺽쇠로 구성된다. 각 속성의 구성은 식별자와 등호 그리고 인용부호 (홑따옴표 또는 겹따옴표)와 텍스트와 객체 그리고 닫는 인용 표식으로 구성된다. 개체 참조는 앰퍼센드와 식별자(또는 숫자 사인 다음에 정수) 그리고 쌍-반점으로 구성된다. 끝 태그는 시작 태그와 비슷하지만, 식별자 앞에 사선이 오고, 속성은 허용되지 않는다. 등등...

그렇지만, 약간만 창조적으로 생각하면, 그것을 다섯개의 토큰 유형으로 축약할 수 있다:

  1. 태그, 좌꺽쇠 (<) 다음에 선택적으로 사선(/), 그리고 식별자로 구성됨
  2. 객체와 문자 참조, 앰퍼센드(&), 다음에 선택적으로 숫자 사인(#), 그리고 기호와 숫자의 문자열로 구성됨.
  3. 텍스트 문자열, 기호와 숫자 그리고 기타 비-특수 문자들(단 공백문자 제외)로 구성된다.
  4. 공백문자(Whitespace).
  5. 특수 문자들 (<, >, &, &apos, ", 그리고=).

어떻게 토큰이 해석될지는 스캐너가 태그 안에 있느냐 아하면 문자 데이터 안에 있느냐에 따라 결정된다. 후자의 경우라면, 식별자와 공백 세그먼트 그리고 특수 문자들은 모두 문자 데이터로 해석된다. 태그 안에 있다면, 그것들은 속성에 사용된다 (속성 이름과 그 값에 모두 사용됨).

다음은 XML 토큰 생성기의 첫 구현이다:

# File: xml-scanner-example-5.py

import re

xml = re.compile(r"""
    <([/?!]?\w+)     # 1. tags
    |&(\#?\w+);      # 2. entities
    |([^<>&'\"=\s]+) # 3. text strings (no special characters)
    |(\s+)           # 4. whitespace
    |(.)             # 5. special characters
    """, re.VERBOSE)

document = """\
<body class='default'>
here&apos;s some text&#33;
</body>
"""

# bind a scanner to the target string
scan = xml.scanner(document)

# print all tokens
while 1:
    m = scan.match()
    if not m:
        break
    print m.lastindex, repr(m.group(m.lastindex))
$ python xml-scanner-example-5.py
1 'body'
4 ' '
3 'class'
5 '='
5 "'"
3 'default'
5 "'"
5 '>'
4 '\n'
3 'here'
2 'apos'
3 's'
4 ' '
3 'some'
4 ' '
3 'text'
2 '#33'
4 '\n'
1 '/body'
5 '>'
4 '\n'

여기에서 lastindex 속성은 태그에 대하여 1, 개체와 문자 참조에 대하여 2, 식별자에 대하여 3, 공백 세그먼트에 대하여 4, 그리고 특수 문자에 대하여 5이다.

토큰 스트림을 시작 태그와 끝 태그 그리고 문자 데이터 섹션으로 돌리는 것은 상대적으로 눈에 보이는 그대로다. 다음 구현에서는 몇 가지 트릭을 사용하여 속도를 높인다 (확실히 눈에 보이는 것은, gettoken라고 부르는 임시로 함수 객체를 만든다. 이 함수는 다음 토큰을 돌려주고, 그 과정에서 공백문자는 가능하면 건너 뛴다).

# File: xmlscanner.py
# a simple xml scanner

import re, string

# xml tokenizer pattern
xml = re.compile("<([/?!]?\w+)|&(#?\w+);|([^<>&'\"=\s]+)|(\s+)|(.)")

def scan(str, target):
    # split string into xml elements

    # create a scanner function for this string
    def gettoken(space=0, scan=xml.scanner(str).match):
        # scanner function (bound to the string)
        try:
            while 1:
                m = scan()
                code = m.lastindex
                text = m.group(m.lastindex)
                if not space or code != 4:
                    return code, text
        except AttributeError:
            raise EOFError

    # token categories
    TAG = 1; ENTITY = 2; STRING = 3; WHITESPACE = 4; SEPARATOR = 5

    start = target.start; end = target.end; data = target.data

    try:
        while 1:
            code, text = gettoken()
            if code == TAG:
                # deal with tags
                type = text[:1]
                if type == "/":
                    # end tag
                    end(text[1:])
                    code, text = gettoken(1)
                    if text != ">":
                        raise SyntaxError, "malformed end tag"
                elif type == "!":
                    # document type declaration (incomplete)
                    value = []
                    while 1:
                        # parse start tag contents
                        code, text = gettoken(1)
                        if text == ">":
                            break
                        value.append(text)
                    value = string.join(value, "")
                else:
                    # start tag or procesing instruction
                    tag = text
                    attrib = {}
                    while 1:
                        # parse start tag contents
                        code, text = gettoken(1)
                        if text == ">":
                            start(tag, attrib)
                            break
                        if text == "/":
                            start(tag, attrib)
                            end(tag)
                            break
                        if text == "?":
                            if type != text:
                                raise SyntaxError, "unexpected quotation mark"
                            code, text = gettoken(1)
                            if text != ">":
                                raise SyntaxError, "expected end tag"
                            try:
                                target.xml(attrib)
                            except AttributeError:
                                pass
                            break
                        if code == STRING:
                            # attribute
                            key = text
                            code, text = gettoken(1)
                            if text != "=":
                                raise SyntaxError, "expected equal sign"
                            code, quote = gettoken(1)
                            if quote != "'" and quote != '"':
                                raise SyntaxError, "expected quote"
                            value = []
                            while 1:
                                code, text = gettoken()
                                if text == quote:
                                    break
                                if code == ENTITY:
                                    try:
                                        text = fixentity(text)
                                    except ValueError:
                                        text = target.resolve_entity(text)
                                value.append(text)
                            attrib[key] = string.join(value, "")
            elif code == ENTITY:
                # text entities
                try:
                    text = fixentity(text)
                except ValueError:
                    text = target.resolve_entity(text)
                data(text)
            else:
                # other text (whitespace, string, or separator)
                data(text)
    except EOFError:
        pass
    except SyntaxError, v:
        # generate nicer error message
        raise

xml_entities = {"amp": "&", "apos": "'", "gt": ">", "lt": "<", "quot": '"'}

def fixentity(entity):
    # map entity name to built-in entity
    try:
        return xml_entities[entity]
    except KeyError:
        pass
    # assume numeric entity (raises ValueError if malformed)
    if entity[:2] == "#x":
        value = int(entity[2:], 16)
    else:
        value = int(entity[1:])
    if value > 127:
        return unichr(value)
    return chr(value)

스캐너는 target 객체에 대하여 메쏘드들을 호출한다. 다음 예제에 보이는 대로 말이다:

# File: xml-scanner-example-6.py

import xmlscanner

class echo:
    def xml(self, attrib):
        print "XML", attrib
    def start(self, tag, attrib):
        print "START", tag, attrib
    def end(self, tag):
        print "END"
    def data(self, text):
        print "DATA", repr(text)

text = """\
<?xml version='1.0'?>
<body class='default'>
here&apos;s some text&#33;
</body>
"""

xmlscanner.scan(text, echo())
$ python xml-scanner-example-6.py
XML {'version': '1.0'}
DATA '\n'
START body {'class': 'default'}
DATA '\n'
DATA 'here'
DATA "'"
DATA 's'
DATA ' '
DATA 'some'
DATA ' '
DATA 'text'
DATA '!'
DATA '\n'
END
DATA '\n'

파이썬 2.1이하에서 이 해석기는 대략 20% 정도 xmllib.py보다 더 빠르다.

요약

이 글에서는 간단한 스캐너 (즉 토큰 생성기)를 파이썬의 새로운 정규 표현식 엔진으로 만드는 법을 연구하였다. 그런 스캐너는 간단한 언어에는 아주 잘 작동하지만, XML 같은 더 복잡한 구문에도 잘 작동하도록 만들 수 있다.

admin: [edit] [new] [validate]
[add a comment!]

Copyright © 2002-2006 by Fredrik Lundh.