메뉴 바로가기 검색 및 카테고리 바로가기 본문 바로가기

한빛출판네트워크

IT/모바일

파이썬으로 재귀하향 파서 만들기(2)

한빛미디어

|

2007-09-11

|

by HANBIT

페이스북 퍼가기 트위터 퍼가기

14,460

제공 : 한빛 네트워크
저자 : Paul McGuire
역자 : 주재경
원문 : Building Recursive Descent Parsers with Python

[이전 기사 보기]
파이썬으로 재귀하향 파서 만들기(1)

예제 프로그램

NaCl, H2O, C6H5OH와 같은 화학 공식을 처리할 필요가 있는 프로그램을 생각해 보자. 이 경우 화학 공식 문법은 하나 혹은 그 이상의 심벌을 가질 것이고 각각의 뒤에는 선택적으로 정수가 올 수 있다. BNF형식으로 이는 다음과 같다. 
integer       :: "0".."9"+
cap           :: "A".."Z"
lower         :: "a".."z"
elementSymbol :: cap lower*
elementRef    :: elementSymbol [ integer ]
formula       :: elementRef+
pyparsing모듈은 Optional과 OneOrMore 클래스로 이 개념을 처리한다. elementSymbol의 정의는 2개의 인자를 갖는 생성자 Word를 사용한다. 첫 번째 인자는 시작 문자를 나타내며 첫 번째 인자 이후 뒤 따르는 문자를 나타낸다. 
caps       = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
lowers     = caps.lower()
digits     = "0123456789"

element    = Word( caps, lowers )
elementRef = element + Optional( Word( digits ) )
formula    = OneOrMore( elementRef )

elements   = formula.parseString( testString )
이것으로 이 프로그램은 아래의 공식을 적절할 토큰으로 처리하는 적절한 토큰화 프로그램이 된다. Pyparsing의 기본 동작은 일치하는 하위 문자열의 하나의 리스트 내에서 파싱된 모든 토큰을 리턴하는 것이다. 
H2O -> ["H", "2", "O"]
C6H5OH -> ["C", "6", "H", "5", "O", "H"]
NaCl -> ["Na", "Cl"]
당연히 리스트 형태로 이 결과를 출력하기에 앞서 이 리턴된 결과로 뭔가를 하고자 할 것이다. 주어진 화학 공식에 대해 분자의 무게를 계산하고자 한다고 가정해 보자. 프로그램은 어딘가에 화학 기호와 여기에 대응되는 원자 무게를 정의해야 한다. 
atomicWeight = {
    "O"  : 15.9994,
    "H"  : 1.00794,
    "Na" : 22.9897,
    "Cl" : 35.4527,
    "C"  : 12.0107,
    ...
    }
결과를 좀더 구조화 시켜 리턴 받고자 하는 경우 파싱된 화학 기호와 관련 양을 좀더 논리적인 그룹으로 만드는 것이 좋다. 다행히도 pyparsing모듈은 이러한 목적에 맞는 Group클래스를 제공한다. elementRef선언을 elementRef = element + Optional( Word( digits ) )에서 다음과 같이 변경한다.elementRef = Group( element + Optional( Word( digits ) ) ) 화학적인 기호로 그룹화된 결과를 얻을 수 있다. 
H2O -> [["H", "2"], ["O"]]
C6H5OH -> [["C", "6"], ["H", "5"], ["O"], ["H"]]
NaCl -> [["Na"], ["Cl"]]
마지막으로 할 내용은 Optional클래스 생성자의 기본 인자를 사용하여 elementRef의 양을 나타내는 부분을 기본 값으로 나타내도록 하는 것이다. 
elementRef = Group( element + Optional( Word( digits ), 
                                default="1" ) )
모든 elementRef는 한 쌍의 값을 리턴한다. Element의 화학 기호화 그 element의 원자 번호가 이에 해당하며 크기가 주어지지 않은 경우 그 값은 1이 된다. 이제 테스크 공식은 element기호와 이에 대응하는 양을 리턴한다. 
H2O -> [["H", "2"], ["O", "1"]]
C6H5OH -> [["C", "6"], ["H", "5"], ["O", "1"], ["H", "1"]]
NaCl -> [["Na", "1"], ["Cl", "1"]]
마지막 단계는 각각에 대해 원자 무게를 계산하는 것이다. parseString을 호출한 후 파이썬 코드 한줄을 추가하면 된다. 
wt = sum( [ atomicWeight[elem] * int(qty) 
                    for elem,qty in elements ] )
결과는 아래와 같다. 
H2O -> [["H", "2"], ["O", "1"]] (18.01528)
C6H5OH -> [["C", "6"], ["H", "5"], ["O", "1"], ["H", "1"]]
        (94.11124)
NaCl -> [["Na", "1"], ["Cl", "1"]] (58.4424)
예제 2는 pyparsing 프로그램 전체를 나타내고 있다.

예제 2 
from pyparsing import Word, Optional, OneOrMore, Group, ParseException

atomicWeight = {
    "O"  : 15.9994,
    "H"  : 1.00794,
    "Na" : 22.9897,
    "Cl" : 35.4527,
    "C"  : 12.0107
    }
    
caps = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
lowers = caps.lower()
digits = "0123456789"

element = Word( caps, lowers )
elementRef = Group( element + Optional( Word( digits ), default="1" ) )
formula = OneOrMore( elementRef )

tests = [ "H2O", "C6H5OH", "NaCl" ]
for t in tests:
    try:
        results = formula.parseString( t )
        print t,"->", results,
    except ParseException, pe:
        print pe
    else:
        wt = sum( [atomicWeight[elem]*int(qty) for elem,qty in results] )
        print "(%.3f)" % wt

========================
H2O -> [["H", "2"], ["O", "1"]] (18.015)
C6H5OH -> [["C", "6"], ["H", "5"], ["O", "1"], ["H", "1"]] (94.111)
NaCl -> [["Na", "1"], ["Cl", "1"]] (58.442)
파서를 이용하여 얻게 되는 좋은 점 중의 하나는 입력 텍스트에 대해 수행하는 타당성 검토이다. wt변수 계산에서 qty문자열이 모두 숫자임을 검사해야 할 필요가 없다는 점에 혹은 올바르지 않은 인자로 인해 발생하는 ValueError를 검사할 필요가 없다는 점에 주의할 것 .

HTML 분석기

마지막 예제로 간단한 HTML 분석기를 만들어 보자. 이것은 파서 표현식에 점수를 매기는 것과 같은 포괄적인HTML 파서는 아니다. 다행히도 대부분의 웹페이지에서 핵심적인 데이터를 추출하기 위한 완벽한 HTML 문법정의가 필요한 것은 아니다. 특히 CGI가 잗동으로 생성한 부분이나 다른 응용 프로그램에 대한 부분이 그렇다.

이 예제는 특정 웹 페이지에 맞춰 제작된 작은 파서로 데이터를 추출한다. 이 경우에 이 페이지는 NIST가 유지하고 있는 가용한 네트워크 타임 프로토콜(NTP)서버 리스트이다. 이 루틴은 어떤 NTP서버가 현재 가용한지를 나타내는 좀더 큰NTP클라이언트 프로그램 한 부분이 될 수도 있다.

HTML분석기를 만들기에 앞서 어떤 종류의 HTML 텍스를 처리하고자 하는지를 알아야 한다. 웹사이트를 방문하고 리턴되는 HTML소스를 보면 웹페이지에는 HTML테이블 내에 NTP서버의 IP주소와 이름이 나열되어 있다.

이름 IP주소 위치
time-a.nist.gov 129.6.15.28 NIST, Gaithersburg, Maryland
time-b.nist.gov 129.6.15.29 NIST, Gaithersburg, Maryland

이 테이블을 위해 HTML은 NTP서버 데이터를 만들기 위해 , ,
태그를 사용한다. 

       ...

이 테이블은 아주 커다란 HTML의 한 부분이다. Pyparsing을 사용하여 주어진 파서 표현식과 일치하는 텍스트를 스캔할 수 있고 전체 입력 텍스트의 한 부분에만 일치하는 파서 표현식을 정의할 수도 있다.



프로그램은 서버의 IP주소와 위치를 추출하므로 문법의 초점을 테이블의 열 방향에만 집중 시킬 수 있다.비 정상적이긴 하지만  패턴과 일치하는 값을 추출하고자 할 수도 있다.


너무 일반적인 표현식은 두 번째의 2개의 열 대신에 첫 번째의 2개의 열에 대응하기 때문에 만큼 일반적인 것과 단지 일치하는 것 이상의 좀더 세부적인 규정을 원한다. 대신에 페이지의 테이블 데이터와 일치하지 않는 부분을 제거하는 좁은 의미의 탐색을 가능하게 하는 규정적인 IP주소를 사용하라.



IP주소를 만들기 위해서는 정수를 정의하고 그 다음에 사이에 마침표를 가진 네 개의 정수를 조합한다.

integer   = Word("0123456789")
ipAddress = integer + "." + integer + "." + integer + "." + integer


HTML태그 를 매칭시킬 필요가 있으며 각각에 대해 파서 요소를 정의한다.

tdStart = Literal("
")

일반적으로 에 모든 것을 다 받아들이는 것이다.pyparsing은 이런 종류의 문법 요소를 위해 SkipTo라는 이름을 가진 클래스를 가지고 있다.



이제 타임서버의 텍스트 패턴 정의에 필요한 모든 것을 가지게 되었다.

timeServer = tdStart + ipAddress + tdEnd + 
                 tdStart + SkipTo(tdEnd) + tdEnd


데이터를 추출하기 위해 timeserver.scanString을 호출하라. 이 함수는 입력 텍스트에 대해 일치하는 각각의 경우에 대해 시작과 마지막 문자열 위치와 일치하는 토큰을 만들어 내는 생성 함수 이다.



예제 3

from pyparsing import *
import urllib

# NTP서버에 대한 기본적인 텍스트 패턴 정의
integer = Word("0123456789")
ipAddress = integer + "." + integer + "." + integer + "." + integer
tdStart = Literal("
")
timeServer =  tdStart + ipAddress + tdEnd + tdStart + SkipTo(tdEnd) + tdEnd

# 타임서버의 리스트를 가져온다
nistTimeServerURL = "http://tf.nist.gov/service/time-servers.html"
serverListPage = urllib.urlopen( nistTimeServerURL )
serverListHTML = serverListPage.read()
serverListPage.close()

for srvrtokens,startloc,endloc in timeServer.scanString( serverListHTML ):
    print srvrtokens

예제 3을 실행하면 다음과 같은 토큰 데이터를 얻는다.

[" 
 ", 
"  "]
["  ", 
"  "]
["  ", 
"  "]
["  ", 
"  "]
:

이 결과를 살펴보면 몇 가지를 바로 알 수 있다. 파서는 IP주소를 구분 마침표와 하위필드를 가진 각각의 토큰으로 기록한다는 것이 한 가지 이다. Pyparsing이 이 필드를 한 개의 문자열 토큰으로 조합하기 위해 파싱하는 동안 몇 가지 일을 할 수 있다면 참 좋을 것이다. Pyparsing  Combine클래스는 이 일을 한다. IP주소에 대해 리턴되는 하나의 문자열 토큰을 얻기위해ipAddress정의를 다음과 같이 수정한다.

ipAddress = Combine( integer + "." + integer + "." + integer + "." + integer )


두 번째로 알 수 있는 것은 결과가 테이블의 열을 표시하는 HTML 태그를 열고 닫는 것을 포함하고 있다. 파싱이 진행되는 동안 이 태그가 중요한 반면에 태그 그 자체는 추출된 데이터에 관심을 두지 않는다. 리턴되는 토큰 데이터에서 이 들을 무시하려면 suppress메서드를 사용한다.

tdStart = Literal("
").suppress()

예제 4

from pyparsing import *
import urllib

# NTP서버에 대한 기본적인 텍스트 패턴 정의
integer = Word("0123456789")
ipAddress = Combine( integer + "." + integer + "." + integer + "." + integer )
tdStart = Literal("
").suppress()
timeServer =  tdStart + ipAddress + tdEnd + tdStart + SkipTo(tdEnd) + tdEnd

# 타임서버 리스트를 가져온다
nistTimeServerURL = "http://tf.nist.gov/service/time-servers.html"
serverListPage = urllib.urlopen( nistTimeServerURL )
serverListHTML = serverListPage.read()
serverListPage.close()

for srvrtokens,startloc,endloc in timeServer.scanString( serverListHTML ):
    print srvrtokens

프로그램 예제4를 실행하여 리턴되는 토큰은 부분적으로 개선되었다.

["129.6.15.28", "NIST, Gaithersburg, Maryland"]
["129.6.15.29", "NIST, Gaithersburg, Maryland"]
["132.163.4.101", "NIST, Boulder, Colorado"]
["132.163.4.102", "NIST, Boulder, Colorado"]


마지막으로 이 토큰에 결과를 더하면 속성 이름으로 이들을 엑세스 할 수 있다. 이것을 하는 가장 손 쉬운 길은 timeServe정의 내에 있다.

timeServer = tdStart + ipAddress.setResultsName("ipAddress") + tdEnd 
        + tdStart + SkipTo(tdEnd).setResultsName("locn") + tdEnd


이제 for루프로 깔금하게 마무리 하고 사전에 데이터 형에 있는 한 멤버처럼 이들을 엑세스 할 수 있다.

servers = {}

for srvrtokens,startloc,endloc in timeServer.scanString( serverListHTML ):
    print "%(ipAddress)-15s : %(locn)s" % srvrtokens
    servers[srvrtokens.ipAddress] = srvrtokens.locn


예제 5 에는 최종 실행 프로그램이 있다.



예제5

from pyparsing import *
import urllib

# NTP서버에 대한 기본적인 텍스트 패턴 정의 
integer = Word("0123456789")
ipAddress = Combine( integer + "." + integer + "." + integer + "." + integer )
tdStart = Literal("
").suppress()
timeServer = tdStart + ipAddress.setResultsName("ipAddress") + tdEnd + 
             tdStart + SkipTo(tdEnd).setResultsName("locn") + tdEnd

# 타임서버 리스트 가져오기
nistTimeServerURL = "http://tf.nist.gov/service/time-servers.html"
serverListPage = urllib.urlopen( nistTimeServerURL )
serverListHTML = serverListPage.read()
serverListPage.close()

servers = {}
for srvrtokens,startloc,endloc in timeServer.scanString( serverListHTML ):
    print "%(ipAddress)-15s : %(locn)s" % srvrtokens
    servers[srvrtokens.ipAddress] = srvrtokens.locn

print servers

이제 성공적으로 NTP서버, IP주소 그리고 프로그램 변수를 성공적으로 추출해서 NTP클라이언트 프로그램은 파싱된 결과를 사용할 수 있다.


결론


Pyparisng은 재귀하향 파서를 만드는 기본적인 프레임 워크를 제공한다. 입력 문자열 스캐닝의 오버헤드 기능에 주의, 일치하는 않는 표현식 처리, 일치하는 것 중 가장 긴 것 선택하기, 콜백함수 호출, 그리고 파싱된 결과를 리턴하는 것이 이 파서의 내용에 속한다. 이로 인해 개발자는 문법 디자인과  이에 대응하는 토큰 처리 구현에만 집중할 수 있다.조합자로서의 pyparsing의 특징으로 인해 개발자는 응용프로그램을 간단한 토큰화 프로그램에서 복잡한 문법 처리기로 확장할 수 있다. 당신의 다음 파싱 프로젝트로 이를 활용하는 것은 아주 훌륭한 방법이다. 


pyparsing 다운받기


저자 Paul McGuire는 Alan Weber & Associates에서 제조시스템 수석컨설턴트로 있다. 여가 시간에 SourceForge의 pyparsing프로젝트를 관리한다. 


역자 참고


파싱 및 문법 구성에 대한 일반적인 내용을 참고하기 위해서는 lex와 yacc(개정판)이 많은 도움이 된다.



역자 주재경님은 현재 (주)세기미래기술에 근무하고 있으며 리눅스, 네트워크, 운영체제 및 멀티미디어 코덱에 관심을 가지고 있습니다.

* e-mail : jkjoo@segifuture.com

											
좋아요

									
TAG : 

        
이전 글 : 
                      파이썬으로 재귀하향 파서 만들기(1)
                  

        
다음 글 : 
                      리눅스 커널 락을 없애려는 시도들
                  

      
				
				
				

               
              
              
				
  					
					
					
					
					
					

	                    

	                    댓글 입력
	                        	                        
	                        
	                    

					
					
				
								
            

        
목록

      

      
      
      

  
    
    

      
      
            
      
            
            
      
      			

				
최신 콘텐츠

				
			
      
      
      
      			

				
인기 콘텐츠

				
			
      
    
자료실

  
  
최근 본 상품0


  

          

        



                

                        Name
                        IP Address
                        Location
                

                

                        time-a.nist.gov
                        129.6.15.28
                        NIST, Gaithersburg, Maryland
                

                

                        time-b.nist.gov
                        129.6.15.29
                        NIST, Gaithersburg, Maryland
                
 IP address   location name 
, , 와 ")
tdEnd   = Literal("태그는 정렬,색깔 등에 대한 속성 구분자를 포함하기도 한다. 그러나 이것은 범용 목적의 파서가 아니라 다행하게도  복잡한 태그를 사용하지 않는 단지 이 웹 페이지에 해당하는 특수 목적으로 작성된 것이다. Pyparsing의 최신 버전은 오프닝 태그에 있는 속성 구분자를 지원하는 HTML태그에 대해 도움을 주는 메서드를 가지고 있다.



마지막으로 서버위치와 일치하는 몇 가지의 표현식이 필요하다. 이것은 실제로 알파벳 데이터, 콤마, 마침표 혹은 숫자를 포함하는지 않는지를 알 길이 없는 자유롭게 만들어진 텍스트이다. 그래서 가장 간단한 선택은 종결 태그		")
tdEnd = Literal("", "129", ".", "6", ".", "15", ".", "28", "", "NIST, Gaithersburg, Maryland", "", "129", ".", "6", ".", "15", ".", "29", "", "NIST, Gaithersburg, Maryland", "", "132", ".", "163", ".", "4", ".", "101", "", "NIST, Boulder, Colorado", "", "132", ".", "163", ".", "4", ".", "102", "", "NIST, Boulder, Colorado", "").suppress()
tdEnd   = Literal("").suppress()
tdEnd = Literal("").suppress()
tdEnd = Literal("