lexer.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "bytes"
  12. "encoding/json"
  13. "fmt"
  14. "regexp"
  15. "strconv"
  16. "strings"
  17. "unicode"
  18. "unicode/utf8"
  19. )
  20. var namePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  21. var numberPattern = regexp.MustCompile("^[0-9].*$")
  22. /*
  23. LexToken represents a token which is returned by the lexer.
  24. */
  25. type LexToken struct {
  26. ID LexTokenID // Token kind
  27. Pos int // Starting position (in bytes)
  28. Val string // Token value
  29. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  30. Lline int // Line in the input this token appears
  31. Lpos int // Position in the input line this token appears
  32. }
  33. /*
  34. NewLexTokenInstance creates a new LexToken object instance from given LexToken values.
  35. */
  36. func NewLexTokenInstance(t LexToken) *LexToken {
  37. return &LexToken{
  38. t.ID,
  39. t.Pos,
  40. t.Val,
  41. t.Identifier,
  42. t.Lline,
  43. t.Lpos,
  44. }
  45. }
  46. /*
  47. Equal checks if this LexToken equals another LexToken. Returns also a message describing
  48. what is the found difference.
  49. */
  50. func (n LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  51. var res = true
  52. var msg = ""
  53. if n.ID != other.ID {
  54. res = false
  55. msg += fmt.Sprintf("ID is different %v vs %v\n", n.ID, other.ID)
  56. }
  57. if !ignorePosition && n.Pos != other.Pos {
  58. res = false
  59. msg += fmt.Sprintf("Pos is different %v vs %v\n", n.Pos, other.Pos)
  60. }
  61. if n.Val != other.Val {
  62. res = false
  63. msg += fmt.Sprintf("Val is different %v vs %v\n", n.Val, other.Val)
  64. }
  65. if n.Identifier != other.Identifier {
  66. res = false
  67. msg += fmt.Sprintf("Identifier is different %v vs %v\n", n.Identifier, other.Identifier)
  68. }
  69. if !ignorePosition && n.Lline != other.Lline {
  70. res = false
  71. msg += fmt.Sprintf("Lline is different %v vs %v\n", n.Lline, other.Lline)
  72. }
  73. if !ignorePosition && n.Lpos != other.Lpos {
  74. res = false
  75. msg += fmt.Sprintf("Lpos is different %v vs %v\n", n.Lpos, other.Lpos)
  76. }
  77. if msg != "" {
  78. var buf bytes.Buffer
  79. out, _ := json.MarshalIndent(n, "", " ")
  80. buf.WriteString(string(out))
  81. buf.WriteString("\nvs\n")
  82. out, _ = json.MarshalIndent(other, "", " ")
  83. buf.WriteString(string(out))
  84. msg = fmt.Sprintf("%v%v", msg, buf.String())
  85. }
  86. return res, msg
  87. }
  88. /*
  89. PosString returns the position of this token in the origianl input as a string.
  90. */
  91. func (t LexToken) PosString() string {
  92. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  93. }
  94. /*
  95. String returns a string representation of a token.
  96. */
  97. func (t LexToken) String() string {
  98. prefix := ""
  99. if !t.Identifier {
  100. prefix = "v:" // Value is not an identifier
  101. }
  102. switch {
  103. case t.ID == TokenEOF:
  104. return "EOF"
  105. case t.ID == TokenError:
  106. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  107. case t.ID == TokenPRECOMMENT:
  108. return fmt.Sprintf("/* %s */", t.Val)
  109. case t.ID == TokenPOSTCOMMENT:
  110. return fmt.Sprintf("# %s", t.Val)
  111. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  112. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  113. case t.ID > TOKENodeKEYWORDS:
  114. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  115. case len(t.Val) > 20:
  116. // Special case for very long values
  117. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  118. }
  119. return fmt.Sprintf("%s%q", prefix, t.Val)
  120. }
  121. // Meta data interface
  122. /*
  123. Type returns the meta data type.
  124. */
  125. func (t LexToken) Type() string {
  126. if t.ID == TokenPRECOMMENT {
  127. return MetaDataPreComment
  128. } else if t.ID == TokenPOSTCOMMENT {
  129. return MetaDataPostComment
  130. }
  131. return MetaDataGeneral
  132. }
  133. /*
  134. Value returns the meta data value.
  135. */
  136. func (t LexToken) Value() string {
  137. return t.Val
  138. }
  139. /*
  140. KeywordMap is a map of keywords - these require spaces between them
  141. */
  142. var KeywordMap = map[string]LexTokenID{
  143. // Sink definition
  144. "sink": TokenSINK,
  145. "kindmatch": TokenKINDMATCH,
  146. "scopematch": TokenSCOPEMATCH,
  147. "statematch": TokenSTATEMATCH,
  148. "priority": TokenPRIORITY,
  149. "suppresses": TokenSUPPRESSES,
  150. // Function definition
  151. "func": TokenFUNC,
  152. // Boolean operators
  153. "and": TokenAND,
  154. "or": TokenOR,
  155. "not": TokenNOT,
  156. // String operators
  157. "like": TokenLIKE,
  158. "hasprefix": TokenHASPREFIX,
  159. "hassuffix": TokenHASSUFFIX,
  160. // List operators
  161. "in": TokenIN,
  162. "notin": TokenNOTIN,
  163. // Constant terminals
  164. "false": TokenFALSE,
  165. "true": TokenTRUE,
  166. "null": TokenNULL,
  167. // Conditional statements
  168. "if": TokenIF,
  169. "elif": TokenELIF,
  170. "else": TokenELSE,
  171. // Loop statements
  172. "for": TokenFOR,
  173. "break": TokenBREAK,
  174. "continue": TokenCONTINUE,
  175. }
  176. /*
  177. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  178. Symbols can be maximal 2 characters long.
  179. */
  180. var SymbolMap = map[string]LexTokenID{
  181. // Condition operators
  182. ">=": TokenGEQ,
  183. "<=": TokenLEQ,
  184. "!=": TokenNEQ,
  185. "==": TokenEQ,
  186. ">": TokenGT,
  187. "<": TokenLT,
  188. // Grouping symbols
  189. "(": TokenLPAREN,
  190. ")": TokenRPAREN,
  191. "[": TokenLBRACK,
  192. "]": TokenRBRACK,
  193. "{": TokenLBRACE,
  194. "}": TokenRBRACE,
  195. // Sequence symbols
  196. ".": TokenDOT,
  197. ",": TokenCOMMA,
  198. ":": TokenCOLON,
  199. ";": TokenSEMICOLON,
  200. // Arithmetic operators
  201. "+": TokenPLUS,
  202. "-": TokenMINUS,
  203. "*": TokenTIMES,
  204. "/": TokenDIV,
  205. "//": TokenDIVINT,
  206. "%": TokenMODINT,
  207. // Assignment statement
  208. ":=": TokenASSIGN,
  209. }
  210. // Lexer
  211. // =====
  212. /*
  213. RuneEOF is a special rune which represents the end of the input
  214. */
  215. const RuneEOF = -1
  216. /*
  217. Function which represents the current state of the lexer and returns the next state
  218. */
  219. type lexFunc func(*lexer) lexFunc
  220. /*
  221. Lexer data structure
  222. */
  223. type lexer struct {
  224. name string // Name to identify the input
  225. input string // Input string of the lexer
  226. pos int // Current rune pointer
  227. line int // Current line pointer
  228. lastnl int // Last newline position
  229. width int // Width of last rune
  230. start int // Start position of the current red token
  231. tokens chan LexToken // Channel for lexer output
  232. }
  233. /*
  234. Lex lexes a given input. Returns a channel which contains tokens.
  235. */
  236. func Lex(name string, input string) chan LexToken {
  237. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  238. go l.run()
  239. return l.tokens
  240. }
  241. /*
  242. LexToList lexes a given input. Returns a list of tokens.
  243. */
  244. func LexToList(name string, input string) []LexToken {
  245. var tokens []LexToken
  246. for t := range Lex(name, input) {
  247. tokens = append(tokens, t)
  248. }
  249. return tokens
  250. }
  251. /*
  252. Main loop of the lexer.
  253. */
  254. func (l *lexer) run() {
  255. if skipWhiteSpace(l) {
  256. for state := lexToken; state != nil; {
  257. state = state(l)
  258. if !skipWhiteSpace(l) {
  259. break
  260. }
  261. }
  262. }
  263. close(l.tokens)
  264. }
  265. /*
  266. next returns the next rune in the input and advances the current rune pointer
  267. if peek is 0. If peek is >0 then the nth character is returned without advancing
  268. the rune pointer.
  269. */
  270. func (l *lexer) next(peek int) rune {
  271. // Check if we reached the end
  272. if int(l.pos) >= len(l.input) {
  273. return RuneEOF
  274. }
  275. // Decode the next rune
  276. pos := l.pos
  277. if peek > 0 {
  278. pos += peek - 1
  279. }
  280. r, w := utf8.DecodeRuneInString(l.input[pos:])
  281. if peek == 0 {
  282. l.width = w
  283. l.pos += l.width
  284. }
  285. return r
  286. }
  287. /*
  288. backup sets the pointer one rune back. Can only be called once per next call.
  289. */
  290. func (l *lexer) backup(width int) {
  291. if width == 0 {
  292. width = l.width
  293. }
  294. l.pos -= width
  295. }
  296. /*
  297. startNew starts a new token.
  298. */
  299. func (l *lexer) startNew() {
  300. l.start = l.pos
  301. }
  302. /*
  303. emitToken passes a token back to the client.
  304. */
  305. func (l *lexer) emitToken(t LexTokenID) {
  306. if t == TokenEOF {
  307. l.emitTokenAndValue(t, "", false)
  308. return
  309. }
  310. if l.tokens != nil {
  311. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false,
  312. l.line + 1, l.start - l.lastnl + 1}
  313. }
  314. }
  315. /*
  316. emitTokenAndValue passes a token with a given value back to the client.
  317. */
  318. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool) {
  319. if l.tokens != nil {
  320. l.tokens <- LexToken{t, l.start, val, identifier, l.line + 1, l.start - l.lastnl + 1}
  321. }
  322. }
  323. /*
  324. emitError passes an error token back to the client.
  325. */
  326. func (l *lexer) emitError(msg string) {
  327. if l.tokens != nil {
  328. l.tokens <- LexToken{TokenError, l.start, msg, false, l.line + 1, l.start - l.lastnl + 1}
  329. }
  330. }
  331. // Helper functions
  332. // ================
  333. /*
  334. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  335. reaches EOF while skipping whitespaces.
  336. */
  337. func skipWhiteSpace(l *lexer) bool {
  338. r := l.next(0)
  339. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  340. if r == '\n' {
  341. l.line++
  342. l.lastnl = l.pos
  343. }
  344. r = l.next(0)
  345. if r == RuneEOF {
  346. l.emitToken(TokenEOF)
  347. return false
  348. }
  349. }
  350. l.backup(0)
  351. return true
  352. }
  353. /*
  354. lexTextBlock lexes a block of text without whitespaces. Interprets
  355. optionally all one or two letter tokens.
  356. */
  357. func lexTextBlock(l *lexer, interpretToken bool) {
  358. r := l.next(0)
  359. if interpretToken {
  360. // Check if we start with a known symbol
  361. nr := l.next(1)
  362. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  363. l.next(0)
  364. return
  365. }
  366. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  367. return
  368. }
  369. }
  370. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  371. if interpretToken {
  372. // Check if we find a token in the block
  373. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  374. l.backup(0)
  375. return
  376. }
  377. nr := l.next(1)
  378. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  379. l.backup(0)
  380. return
  381. }
  382. }
  383. r = l.next(0)
  384. }
  385. if r != RuneEOF {
  386. l.backup(0)
  387. }
  388. }
  389. /*
  390. lexNumberBlock lexes a block potentially containing a number.
  391. */
  392. func lexNumberBlock(l *lexer) {
  393. r := l.next(0)
  394. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  395. if !unicode.IsNumber(r) && r != '.' {
  396. if r == 'e' {
  397. l1 := l.next(1)
  398. l2 := l.next(2)
  399. if l1 != '+' || !unicode.IsNumber(l2) {
  400. break
  401. }
  402. l.next(0)
  403. l.next(0)
  404. } else {
  405. break
  406. }
  407. }
  408. r = l.next(0)
  409. }
  410. if r != RuneEOF {
  411. l.backup(0)
  412. }
  413. }
  414. // State functions
  415. // ===============
  416. /*
  417. lexToken is the main entry function for the lexer.
  418. */
  419. func lexToken(l *lexer) lexFunc {
  420. // Check if we got a quoted value or a comment
  421. n1 := l.next(1)
  422. n2 := l.next(2)
  423. // Parse comments
  424. if (n1 == '/' && n2 == '*') || n1 == '#' {
  425. return lexComment
  426. }
  427. // Parse strings
  428. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  429. return lexValue
  430. }
  431. // Lex a block of text and emit any found tokens
  432. l.startNew()
  433. // First try to parse a number
  434. lexNumberBlock(l)
  435. keywordCandidate := strings.ToLower(l.input[l.start:l.pos])
  436. // Check for number
  437. if numberPattern.MatchString(keywordCandidate) {
  438. _, err := strconv.ParseFloat(keywordCandidate, 64)
  439. if err == nil {
  440. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false)
  441. return lexToken
  442. }
  443. }
  444. if len(keywordCandidate) > 0 {
  445. l.backup(l.pos - l.start)
  446. }
  447. lexTextBlock(l, true)
  448. keywordCandidate = strings.ToLower(l.input[l.start:l.pos])
  449. // Check for keyword
  450. token, ok := KeywordMap[keywordCandidate]
  451. if !ok {
  452. // Check for symbol
  453. token, ok = SymbolMap[keywordCandidate]
  454. }
  455. if ok {
  456. // A known token was found
  457. l.emitToken(token)
  458. } else {
  459. if !namePattern.MatchString(keywordCandidate) {
  460. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  461. return nil
  462. }
  463. // An identifier was found
  464. l.emitTokenAndValue(TokenIDENTIFIER, keywordCandidate, true)
  465. }
  466. return lexToken
  467. }
  468. /*
  469. lexValue lexes a string value.
  470. Values can be declared in different ways:
  471. ' ... ' or " ... "
  472. Characters are parsed between quotes (escape sequences are interpreted)
  473. r' ... ' or r" ... "
  474. Characters are parsed plain between quote
  475. */
  476. func lexValue(l *lexer) lexFunc {
  477. var endToken rune
  478. l.startNew()
  479. allowEscapes := false
  480. r := l.next(0)
  481. // Check if we have a raw quoted string
  482. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  483. endToken = q
  484. l.next(0)
  485. } else {
  486. allowEscapes = true
  487. endToken = r
  488. }
  489. r = l.next(0)
  490. rprev := ' '
  491. lLine := l.line
  492. lLastnl := l.lastnl
  493. for (!allowEscapes && r != endToken) ||
  494. (allowEscapes && (r != endToken || rprev == '\\')) {
  495. if r == '\n' {
  496. lLine++
  497. lLastnl = l.pos
  498. }
  499. rprev = r
  500. r = l.next(0)
  501. if r == RuneEOF {
  502. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  503. return nil
  504. }
  505. }
  506. if allowEscapes {
  507. val := l.input[l.start+1 : l.pos-1]
  508. // Interpret escape sequences right away
  509. if endToken == '\'' {
  510. // Escape double quotes in a single quoted string
  511. val = strings.Replace(val, "\"", "\\\"", -1)
  512. }
  513. s, err := strconv.Unquote("\"" + val + "\"")
  514. if err != nil {
  515. l.emitError(err.Error() + " while parsing string")
  516. return nil
  517. }
  518. l.emitTokenAndValue(TokenSTRING, s, true)
  519. } else {
  520. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], true)
  521. }
  522. // Set newline
  523. l.line = lLine
  524. l.lastnl = lLastnl
  525. return lexToken
  526. }
  527. /*
  528. lexComment lexes comments.
  529. */
  530. func lexComment(l *lexer) lexFunc {
  531. // Consume initial /*
  532. r := l.next(0)
  533. if r == '#' {
  534. l.startNew()
  535. for r != '\n' && r != RuneEOF {
  536. r = l.next(0)
  537. }
  538. l.emitTokenAndValue(TokenPOSTCOMMENT, l.input[l.start:l.pos], false)
  539. if r == RuneEOF {
  540. return nil
  541. }
  542. l.line++
  543. } else {
  544. l.next(0)
  545. lLine := l.line
  546. lLastnl := l.lastnl
  547. l.startNew()
  548. r = l.next(0)
  549. for r != '*' && l.next(1) != '/' {
  550. if r == '\n' {
  551. lLine++
  552. lLastnl = l.pos
  553. }
  554. r = l.next(0)
  555. if r == RuneEOF {
  556. l.emitError("Unexpected end while reading comment")
  557. return nil
  558. }
  559. }
  560. l.emitTokenAndValue(TokenPRECOMMENT, l.input[l.start:l.pos-1], false)
  561. // Consume final /
  562. l.next(0)
  563. // Set newline
  564. l.line = lLine
  565. l.lastnl = lLastnl
  566. }
  567. return lexToken
  568. }